fork download
copy 
  1. ; random total
  2.  
  3. (define (range . args)
  4.   (case (length args)
  5.     ((1) (range 0 (car args) (if (negative? (car args)) -1 1)))
  6.     ((2) (range (car args) (cadr args) (if (< (car args) (cadr args)) 1 -1)))
  7.     ((3) (let ((le? (if (negative? (caddr args)) >= <=)))
  8.            (let loop ((x(car args)) (xs '()))
  9.              (if (le? (cadr args) x)
  10.                  (reverse xs)
  11.                  (loop (+ x (caddr args)) (cons x xs))))))
  12.     (else (error 'range "unrecognized arguments"))))
  13.  
  14. (define (add1 n) (+ n 1))
  15.  
  16. (define sort #f)
  17. (define merge #f)
  18. (let ()
  19.   (define dosort
  20.     (lambda (pred? ls n)
  21.       (if (= n 1)
  22.           (list (car ls))
  23.           (let ((i (quotient n 2)))
  24.             (domerge pred?
  25.                      (dosort pred? ls i)
  26.                      (dosort pred? (list-tail ls i) (- n i)))))))
  27.   (define domerge
  28.     (lambda (pred? l1 l2)
  29.       (cond
  30.         ((null? l1) l2)
  31.         ((null? l2) l1)
  32.         ((pred? (car l2) (car l1))
  33.          (cons (car l2) (domerge pred? l1 (cdr l2))))
  34.         (else (cons (car l1) (domerge pred? (cdr l1) l2))))))
  35.   (set! sort
  36.     (lambda (pred? l)
  37.       (if (null? l) l (dosort pred? l (length l)))))
  38.   (set! merge
  39.     (lambda (pred? l1 l2)
  40.       (domerge pred? l1 l2))))
  41.  
  42. (define rand #f)
  43. (define randint #f)
  44. (let ((two31 #x80000000) (a (make-vector 56 -1)) (fptr #f))
  45.   (define (mod-diff x y) (modulo (- x y) two31)) ; generic version
  46.   ; (define (mod-diff x y) (logand (- x y) #x7FFFFFFF)) ; fast version
  47.   (define (flip-cycle)
  48.     (do ((ii 1 (+ ii 1)) (jj 32 (+ jj 1))) ((< 55 jj))
  49.       (vector-set! a ii (mod-diff (vector-ref a ii) (vector-ref a jj))))
  50.     (do ((ii 25 (+ ii 1)) (jj 1 (+ jj 1))) ((< 55 ii))
  51.       (vector-set! a ii (mod-diff (vector-ref a ii) (vector-ref a jj))))
  52.     (set! fptr 54) (vector-ref a 55))
  53.   (define (init-rand seed)
  54.     (let* ((seed (mod-diff seed 0)) (prev seed) (next 1))
  55.       (vector-set! a 55 prev)
  56.       (do ((i 21 (modulo (+ i 21) 55))) ((zero? i))
  57.         (vector-set! a i next) (set! next (mod-diff prev next))
  58.         (set! seed (+ (quotient seed 2) (if (odd? seed) #x40000000 0)))
  59.         (set! next (mod-diff next seed)) (set! prev (vector-ref a i)))
  60.       (flip-cycle) (flip-cycle) (flip-cycle) (flip-cycle) (flip-cycle)))
  61.   (define (next-rand)
  62.     (if (negative? (vector-ref a fptr)) (flip-cycle)
  63.       (let ((next (vector-ref a fptr))) (set! fptr (- fptr 1)) next)))
  64.   (define (unif-rand m)
  65.     (let ((t (- two31 (modulo two31 m))))
  66.       (let loop ((r (next-rand)))
  67.         (if (<= t r) (loop (next-rand)) (modulo r m)))))
  68.   (init-rand 19380110) ; happy birthday donald e knuth
  69.   (set! rand (lambda seed
  70.     (cond ((null? seed) (/ (next-rand) two31))
  71.           ((eq? (car seed) 'get) (cons fptr (vector->list a)))
  72.           ((eq? (car seed) 'set) (set! fptr (caadr seed))
  73.                                  (set! a (list->vector (cdadr seed))))
  74.           (else (/ (init-rand (modulo (numerator
  75.                   (inexact->exact (car seed))) two31)) two31)))))
  76.   (set! randint (lambda args
  77.     (cond ((null? (cdr args))
  78.             (if (< (car args) two31) (unif-rand (car args))
  79.               (floor (* (next-rand) (car args)))))
  80.           ((< (car args) (cadr args))
  81.             (let ((span (- (cadr args) (car args))))
  82.               (+ (car args)
  83.                  (if (< span two31) (unif-rand span)
  84.                    (floor (* (next-rand) span))))))
  85.           (else (let ((span (- (car args) (cadr args))))
  86.                   (- (car args)
  87.                      (if (< span two31) (unif-rand span)
  88.                        (floor (* (next-rand) span))))))))))
  89.  
  90. (define (shuffle x)
  91.   (do ((v (list->vector x)) (n (length x) (- n 1)))
  92.       ((zero? n) (vector->list v))
  93.     (let* ((r (randint n)) (t (vector-ref v r)))
  94.       (vector-set! v r (vector-ref v (- n 1)))
  95.       (vector-set! v (- n 1) t))))
  96.  
  97. (define (diffs xs)
  98.   (let loop ((xs xs) (ds (list)))
  99.     (if (null? (cdr xs)) (reverse ds)
  100.       (loop (cdr xs) (cons (- (cadr xs) (car xs)) ds)))))
  101.  
  102. (define (rand-total k n)
  103.   (let* ((n-k (- n k)) (k-1 (- k 1))
  104.          (rs (map (lambda (x) (randint n-k)) (range k-1)))
  105.          (ds (diffs (cons 0 (append (sort < rs) (list n-k))))))
  106.     (shuffle (map add1 ds))))
  107.  
  108. (display (rand-total 17 1000)) (newline)
Success #stdin #stdout 0.09s 8896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(81 31 40 121 83 195 154 17 5 59 6 14 109 11 42 14 18)
https://ideone.com/o5fT8t
language:
Scheme (guile 2.2.4)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!