random-sequence

[Sammo]

To generate a random sequence of integers, this seems to work well. Is there a better way?

Code Select Expand

(define (random-sequence n m)
    (letn ( s (sequence n m) j (length s) )
        (dotimes (x (* j 10)) (swap (rand j) (rand j) s))
        s ))

[Lutz]

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

[Sammo]

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.

[Lutz]

Oops, sorry, should have read your code more carefully, here is another faster solution:

Code Select Expand


(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)

[Sammo]

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

[Lutz]

YES, thanks, I corrected the post



Lutz

[newdep]

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)))

[eddier]

Another version.

Code Select Expand


(define (random-sequence n m)
    (let (L (sequence 1 10))
      (map (lambda (x) (pop L x)) (rand m m))))


Ed

[eddier]

Oops.

Code Select Expand


(define (random-sequence n m)
    (let (L (sequence n m))
      (map (lambda (x) (pop L x)) (rand m m))))


Ed.

[Sammo]

Hi eddier,



I think you version works better like this:

Code Select Expand

(define (random-sequence n m)
    (letn (L (sequence n m) N (length L))
      (map (lambda (x) (pop L x)) (rand N N)) ))

[eddier]

Yep you are right!



Ed

[Fanda]

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

[Fanda]

How big is the chance?

Code Select Expand

; 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:

Code Select Expand

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

[Lutz]

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

[Fanda]

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