newlispfanclub.alh.net

Posted: **Wed Dec 08, 2004 9:16 pm**

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

Posted: **Wed Dec 08, 2004 10:27 pm**

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

Posted: **Wed Dec 08, 2004 10:59 pm**

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.

Posted: **Wed Dec 08, 2004 11:20 pm**

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)

Posted: **Wed Dec 08, 2004 11:44 pm**

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

Posted: **Thu Dec 09, 2004 1:30 am**

YES, thanks, I corrected the post

Lutz

Posted: **Wed Aug 17, 2005 7:54 pm**

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

Posted: **Thu Aug 18, 2005 2:50 pm**

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

Posted: **Thu Aug 18, 2005 2:52 pm**

Oops.

Code: Select all

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

Ed.

Posted: **Thu Aug 18, 2005 3:05 pm**

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

Posted: **Thu Aug 18, 2005 3:13 pm**

Yep you are right!

Ed

Posted: **Sat Aug 27, 2005 6:43 pm**

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

Posted: **Sat Aug 27, 2005 7:13 pm**

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

Posted: **Sat Aug 27, 2005 8:18 pm**

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

Posted: **Sun Aug 28, 2005 1:54 am**

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

Posted: **Tue Oct 18, 2005 7:08 am**

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