random-sequence

[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 Expand

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

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

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

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

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


Code Select Expand

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