Topic: how to shuffle a set of list ?

[RAIN CODE]

hi guys,

Do you know how to shuffle a set of list ? Let say I have a name list (list "Adam Ben Candy Danny Einstein Frank Gilbert")
and shuffle name list differently each time. Result = (list "Einstein Gilbert Ben Danny Adam Candy Frank ")

Thanks.

[CAB]

Generate random numbers in the range zero to (1- (length lst))
Collect the random numbers in a list ignoring repeats, then sort the name list using that random number list as an index.

[RAIN CODE]

Actually this lisp is for showing my appreciation to the people here who have given their help/tips/suggestions to me, when I have problem writing the game.
It will display the people's name before game start. I thought of putting names not in any favor of the people so i thought of showing the names in random like in photoshop when you start the program you see name arrange in randomly, each time you start the program.

[RAIN CODE]

I know how to write random numbers.
But I don't know how to shuffle the list names. Could someone help me on this ?

Thanks

[irneb]

You mean something like this:

Code - Auto/Visual Lisp: [Select]

1. (defun ShuffleList (lst / ilst p n res)
2.   (repeat (setq n (length lst)) (setq ilst (cons (setq n (1- n)) ilst)))
3.   (repeat (length ilst)
4.     (setq p (RandomMinMax 0 (length ilst) nil)
5.           res (cons (nth (setq n (nth p ilst)) lst) res)
6.           ilst (vl-remove n ilst)))
7.   res)
8.                  
9.  
10. ;;; -------------------------------------------------------------------------------------
11. ;;; Pseudo random number generator between minimum & maximum values
12. ;;; -------------------------------------------------------------------------------------
13. ;;; minimum: The minimum value
14. ;;; maximum: The maximum value
15. ;;; seed   : A number as the seed, nil to auto-generate
16. ;;; Result : real value between 0.0 and 1.0
17. ;;; -------------------------------------------------------------------------------------
18. (defun RandomMinMax  (minimum maximum seed / diff rand)
19.   (setq diff    (max minimum maximum)
20.         minimum (min minimum maximum)
21.         maximum diff
22.         diff    (- maximum minimum)
23.         rand    (Random seed))
24.   (if (= (type minimum) (type maximum) 'INT)
25.     (fix (+ minimum (* diff rand)))
26.     (+ minimum (* diff rand))))
27.  
28. ;;; -------------------------------------------------------------------------------------
29. ;;; Pseudo random number generator
30. ;;; -------------------------------------------------------------------------------------
31. ;;; seed : A number as the seed, nil to auto-generate
32. ;;; Result: real value between 0.0 and 1.0
33. ;;; -------------------------------------------------------------------------------------
34. (defun Random  (seed /)
35.   (if (not seed)
36.     (setq seed (if *random:seed*
37.                  *random:seed*
38.                  (setq *random:seed* (getvar "DATE"))))
39.     (setq *random:seed* seed))
40.   (setq seed          (rem (+ (* 25173 seed) 13849) 65536)
41.         *random:seed* seed)
42.   (/ seed 65536))

[Stefan]

Code: [Select]

(defun shuffle (l / n i l1)
  (setq n (length l))
  (while (< (length l1) n)
    (if (not (member (setq i (rem (dos_random) n)) l1)) (setq l1 (cons i l1)))
    )
  (mapcar '(lambda (x) (nth x l)) l1)
  )

[irneb]

Stefan,be careful with that approach: it might run for a long time. The way you attempt to bypass the possible duplicates from the random function is a hit-and-miss approach. You've got no guarantee that it will find all individual indexes, it might find the same index 100's (if not 1000's) of times.

Mine does seem inefficient, but only because it loops twice through the list and uses nth twice as well. Yours has a best case performance of also only looping 2x (i.e. while & mapcar), but a worst case performance of looping infinitely.

To optimize mine, here's a version which only loops once (using the same Randoms as before):

Code - Auto/Visual Lisp: [Select]

1. (defun ShuffleList2 (lst / val res)
2.   (repeat (length lst)
3.     (setq res (cons (setq val (nth (RandomMinMax 0 (length lst) nil) lst)) res)
4.           lst (vl-remove val lst)))
5.   res)

Though this one errors if there's duplicates in the original list.

[irneb]

As example why I say yours is dangerous:

Code: [Select]

_$ (setq lst nil n 0)
0
_$ (length (repeat 50 (setq lst (cons (setq n (1+ n)) lst))))
50
_$ (QuickBench '((ShuffleList lst) (ShuffleList2 lst) (shuffle lst)))
Benchmarking ... done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(SHUFFLELIST2 LST)                            2048      1326      1326     20.33
(SHUFFLELIST LST)                             2048      1560      1560     17.28
(SHUFFLE LST)                                  128      1685     26960      1.00
--------------------------------------------------------------------------------
I've tried it on a list of 1000 items ... and had to Ctrl+Break after 20 minutes.

[Stefan]

Stefan,be careful with that approach: it might run for a long time. The way you attempt to bypass the possible duplicates from the random function is a hit-and-miss approach. You've got no guarantee that it will find all individual indexes, it might find the same index 100's (if not 1000's) of times.

You are right. Here is another variant, 3 iterations. Works with duplicates too

Code - Auto/Visual Lisp: [Select]

1. (defun ph:shuffle1 (l / n i l1 l2)
2.   (repeat (setq n (length l))
3.     (setq l1 (cons (setq n (1- n)) l1))
4.     )
5.   (repeat (setq n (length l))
6.     (setq l2 (cons (setq i (nth (rem (dos_random) (- n (length l2))) l1)) l2)
7.           l1 (vl-remove i l1)
8.           )
9.     )
10.   (mapcar '(lambda (x) (nth x l)) l2)
11.   )

I've tried it on a list of 1000 items ... and had to Ctrl+Break after 20 minutes.

If you wanted to say 10 000 I believe you. Though, I think RAIN CODE doesn't have such a large list...
1000 item are generated in less than a second.

Code - Auto/Visual Lisp: [Select]

1. (defun run_time (/ time n l1)
2.   (setq time (getvar 'millisecs)
3.         n    1000
4.   )
5.   (while (< (length l1) n)
6.     (if (not (member (setq i (rem (dos_random) n)) l1))
7.       (setq l1 (cons i l1))
8.     )
9.   )
10.   (princ (- (getvar 'millisecs) time))
11.   (princ)
12. )
13. _$ (run_time)
14. 797
15. _$ (run_time)
16. 719
17. _$ (run_time)
18. 796
19. _$ (run_time)
20. 625
21. _$ (run_time)
22. 765
23. _$  

[irneb]

You might be correct about the 10000/1000 though ... ACad crashed so I couldn't see the history in VLIDE to be sure. It's not uncommon for me to get more than one character when typing on this below avg M$ keyboard 

Anyhow, here's another alternative (works on duplicates as well):

Code - Auto/Visual Lisp: [Select]

1. (defun ShuffleList3  (lst / pivot)
2.   (setq pivot (/ (length lst) 2))
3.   (mapcar '(lambda (n) (nth n lst))
4.           (vl-sort-i lst '(lambda (a b) (<= (RandomMinMax 0 (length lst) nil) pivot)))))

Or one which doesn't use nth, but removes duplicates:

Code - Auto/Visual Lisp: [Select]

1. (defun ShuffleList4  (lst / pivot)
2.   (setq pivot (/ (length lst) 2))
3.   (vl-sort lst '(lambda (a b) (<= (RandomMinMax 0 (length lst) nil) pivot))))

Though they're not as fast as my originals:

Code: [Select]

$ (setq lst nil n 0)
0
_$ (length (repeat 50 (setq lst (cons (setq n (1+ n)) lst))))
50
_$ (QuickBench '((ShuffleList lst) (ShuffleList2 lst) (shuffle lst) (ph:shuffle1 lst) (ShuffleList3 lst) (ShuffleList4 lst)))
Benchmarking ...... done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(SHUFFLELIST2 LST)                            2048      1904      1904     21.23
(SHUFFLELIST LST)                             2048      2059      2059     19.63
(SHUFFLELIST4 LST)                             512      1357      5428      7.45
(SHUFFLELIST3 LST)                             512      1466      5864      6.89
(PH:SHUFFLE1 LST)                              256      1154      9232      4.38
(SHUFFLE LST)                                   64      1263     40416      1.00
--------------------------------------------------------------------------------

[Lee Mac]

Nothing new:

Code - Auto/Visual Lisp: [Select]

1. (defun LM:shuffle ( l / i n r )
2.     (repeat (setq n (length l))
3.         (setq r (cons (nth (setq i (LM:randomrange 0 (setq n (1- n)))) l) r)
4.               l (LM:removenth i l)
5.         )
6.     )
7.     r
8. )
9.  
10. (defun LM:removenth ( n l )
11.     (if (and l (< 0 n))
12.         (cons (car l) (LM:removenth (1- n) (cdr l)))
13.         (cdr l)
14.     )
15. )
16.  
17. (defun LM:random ( / x )
18.     (/ (setq x 4294967296.0 seed (rem (1+ (* 1664525.0 (cond (seed) ((getvar 'DATE))))) x)) x)
19. )
20.  
21. (defun LM:randomrange ( a b )
22.     (fix (+ a (* (LM:random) (- b a -1))))
23. )

Just a variation of the Knuth Shuffle

[irneb]

I think your removeNth function makes it a bit less efficient:

Code: [Select]

Benchmarking ....... done for 1024 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(SHUFFLELIST LST)                             1024      1061      1061     18.82
(SHUFFLELIST2 LST)                            1024      1107      1107     18.04
(LM:SHUFFLE LST)                               512      1185      2370      8.43
(SHUFFLELIST4 LST)                             512      1419      2838      7.04
(SHUFFLELIST3 LST)                             512      1578      3156      6.33
(PH:SHUFFLE1 LST)                              256      1217      4868      4.10
(SHUFFLE LST)                                   64      1248     19968      1.00
--------------------------------------------------------------------------------But still ... good one Lee!

[Lee Mac]

Thank you Irneb 

For this particular task, judging by the OP's description, I very much doubt that raw performance will be an issue, however, if a comparison is to be made, in my opinion the functions retaining / removing duplicates should be compared separately, else we are not comparing apples with apples, since, by the nature of the functions available in LISP, more code is inevitably required to remove a single instance of an item.

[irneb]

You're absolutely correct. My ShuffleList2 & -4 should then be removed from the test.

BTW, a slightly optimized version of yours, though I don't particularly like this one (I think it's a bit forced):

Code - Auto/Visual Lisp: [Select]

1. (defun ShuffleList5  (lst / idx tmp res)
2.   (repeat (length lst)
3.     (setq idx (- (RandomMinMax 0 (+ (length tmp) (length lst)) nil) (length tmp)))
4.     (cond ((> idx 0) (repeat idx (setq tmp (cons (car lst) tmp) lst (cdr lst)))
5.            (setq res (cons (car tmp) res) tmp (cdr tmp)))
6.           ((< idx 0) (repeat (abs idx) (setq lst (cons (car tmp) lst) tmp (cdr tmp)))
7.            (setq res (cons (car lst) res) lst (cdr lst)))
8.           (tmp (setq res (cons (car tmp) res) tmp (cdr tmp)))
9.           (t (setq res (cons (car lst) res) lst (cdr lst)))))
10.   res)

Speed's not that great either:

Code: [Select]

Benchmarking ..... done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(SHUFFLELIST2 LST)                            2048      1764      1764      4.74
(SHUFFLELIST LST)                             1024      1030      2060      4.06
(SHUFFLELIST5 LST)                             512      1000      4000      2.09
(LM:SHUFFLE LST)                               512      1045      4180      2.00
(PH:SHUFFLE1 LST)                              256      1046      8368      1.00
--------------------------------------------------------------------------------Not to mention, you're also correct: the OP's probably not going to be very concerned about fractions of seconds 

[highflyingbird]

If use safearray, is much faster,maybe you don't like this style

Code - Auto/Visual Lisp: [Select]

1. ;;;highflybird 2012.7.25
2. (defun HFB:shuffle (lst / count array i lastIndex RandNum tmp)
3.   (setq count (length lst))
4.   (setq Array (MakeSafeArray lst vlax-vblong))                     ;->maybe other type
5.   (setq i 0)
6.   (setq LastIndex (1- count))
7.   (repeat LastIndex
8.     (setq RandNum (LM:randomrange i LastIndex))
9.     (setq tmp (vlax-safearray-get-element array RandNum))
10.     (vlax-safearray-put-element array RandNum (vlax-safearray-get-element array i))
11.     (vlax-safearray-put-element array i tmp)
12.     (setq i (1+ i))
13.   )
14.   (vlax-safearray->list array)
15. )
16. (defun MakeSafeArray (L DataType)
17.   (vlax-safearray-fill (vlax-make-safearray DataType (cons 0 (1- (length L)))) L)
18. )
19.