To generate a random sequence of integers, this seems to work well. Is there a better way?
(define (random-sequence n m)
(letn ( s (sequence n m) j (length s) )
(dotimes (x (* j 10)) (swap (rand j) (rand j) s))
s ))
YES, for evenly distributed integers:
(rand r n) ; r=range, n=number in sequence
(rand 3 10) => (2 0 2 0 0 1 2 1 1 0)
or for even distributed floats:
(random m d n) => m=mean, d=deviation, n=number in sequence
(random 5 1 10) => (5.677205725 5.056215094 ... 5.726493118)
and the same for normal distributed floats:
(normal m s n) => m=mean, s=standard dev, n=number in sequence
its all in the manual, use (seed ...) for setting initialrandom number seed.
Lutz
Okay, thanks!
I guess I meant to say "randomly ordered sequence of non-repeating integers" in the same manner that 'sequence' produces an ordered such sequence.
Oops, sorry, should have read your code more carefully, here is another faster solution:
(define (random-sequence n m)
(letn (s (sequence n m) j (length s) result '())
(for (i j 1)
(push (pop s (rand i)) result))
result))
(random-sequence 1 10) => (1 6 8 9 10 3 5 7 2 4)
Lutz
corrected (rand j) -> (rand i)
Wonderful! Much faster and easier to read, too. Thanks for the lesson! Should that be '(pop s (rand i))' instead of '(pop s (rand j))'?
-- Sam
YES, thanks, I corrected the post
Lutz
Aaaaaaaa I needed this ;-)
I knew someone already had the need for this one ;-)
Its a listing in the FAQ worthy Lutz!!!
--- love it!!!
(define (random-sequence n m)
(letn (s (sequence n m) j (length s) result '())
(for (i j 1)
(push (pop s (rand i)) result))
result))
(random-sequence 1 10) => (1 6 8 9 10 3 5 7 2 4)
---
The smalest i could find was, but not satisfying enough ->
(define (srand) (unique (rand 9 81)))
Another version.
(define (random-sequence n m)
(let (L (sequence 1 10))
(map (lambda (x) (pop L x)) (rand m m))))
Ed
Oops.
(define (random-sequence n m)
(let (L (sequence n m))
(map (lambda (x) (pop L x)) (rand m m))))
Ed.
Hi eddier,
I think you version works better like this:
(define (random-sequence n m)
(letn (L (sequence n m) N (length L))
(map (lambda (x) (pop L x)) (rand N N)) ))
Yep you are right!
Ed
Just wanted to let you know... There is a chance that by calling 'rand' - even several times - you can get exactly the same sequence as the one you started with, because 'rand' will generate indexes (N-1 N-2 ... 0) where N is the length of the sequence.
If you try (random-sequence 0 1), there is a 50% chance for this.
In Lutz's version it would mean, that: EVERY time (rand i) = i-1
And that's possible.
Because of this we might add some check at the end of the function and run it again in case that it was the same.
Lutz, you might consider this before implementing the 'shuffle'.
Fanda
How big is the chance?
; chance that the sequence will be the same: (1 / N!)
(define (chance N)
(div 1 (exp (gammaln (+ N 1)))))
; N = 1..10
(for (x 1 10)
(println (format "N = %2d %9.5f" x (mul (chance x) 100)) " %"))
Result:
N = 1 100.00000 %
N = 2 50.00000 %
N = 3 16.66667 %
N = 4 4.16667 %
N = 5 0.83333 %
N = 6 0.13889 %
N = 7 0.01984 %
N = 8 0.00248 %
N = 9 0.00028 %
N = 10 0.00003 %
-- Fanda
Good point, i will keep this in mind: shuffle would randomize the input sequence and shuffle again it again if it doesn't differ from the input.
Lutz
The chance that it will be the same:
after 2 runs: (1 / N!)^2
after 3 runs: (1 / N!)^3
after X runs: (1 / N!)^X
For small N it could run several times. For big N it should be Ok.
The thing is: Once in a lifetime it could take a long time to shuffle something.
It could be a good idea to put some limit on how many times it was ran. If it exceeds the limit, use some straight method to shuffle (like exchange half of list with other half).
Fanda
Yet another way how to shuffle the list:
Function 'factorial'
; n = 0..10
(define (factorial n)
('(1 1 2 6 24 120 720 5040 40320 362880 3628800) n))
Function creating the nth combination:
;
; nth possible combination of the list
;
(define (nth-combination lst i)
(let (len (length lst))
(if (or (< i 0) (>= i (factorial len)))
(throw-error "Bad index..."))
(if (<= len 1)
lst
(let (n 0 d 0 result '())
(dotimes (x len)
(setq n (factorial (- (- len x) 1)))
(setq d (/ i n))
(setq i (% i n))
(push (pop lst d) result -1))
result))))
And finally our new randomize function:
(define (new-randomize lst bool)
(let (len (length lst))
(if (<= len 1)
lst
(if bool
(nth-combination lst (rand (factorial len)))
(nth-combination lst (+ 1 (rand (- (factorial len) 1))))))))
(setq L '(1 2 3))
(setq len (length L))
(println)
(dotimes (x (factorial len))
(println x " -> " (nth-combination L x)))
0 -> (1 2 3)
1 -> (1 3 2)
2 -> (2 1 3)
3 -> (2 3 1)
4 -> (3 1 2)
5 -> (3 2 1)
- runs only once => predictable and in the average faster than re-running
- needs factorial
- calculations with large numbers if list is longer than 10 => since the biggest chances for re-running are only for the small lengths, it is still useful :-)
Fanda