random-sequence

[Sammo]

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

Code: Select all

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

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

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

Ed

[eddier]

Oops.

Code: Select all

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

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

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

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

[Fanda]

Yet another way how to shuffle the list:

Idea: We are looking for one of the possible combinations of the sequence (or the list). For list of the length N, there is N! combinations. We could generate the list containing all these combinations and simply pick one using the index. What is also possible - we can create the combination using only the index.

We need:
Function 'factorial'

Code: Select all

; n = 0..10
(define (factorial n)
  ('(1 1 2 6 24 120 720 5040 40320 362880 3628800) n))

Function creating the nth combination:

Code: Select all

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

Code: Select all

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

To test our 'nth-combination' function:

Code: Select all

(setq L '(1 2 3))
(setq len (length L))

(println)
(dotimes (x (factorial len))
  (println x " -> " (nth-combination L x)))

Code: Select all

0 -> (1 2 3)
1 -> (1 3 2)
2 -> (2 1 3)
3 -> (2 3 1)
4 -> (3 1 2)
5 -> (3 2 1)

Pros:
- runs only once => predictable and in the average faster than re-running

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