TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: RAIN CODE on July 24, 2012, 10:49:59 PM

Title: how to shuffle a set of list ?
Post by: RAIN CODE on July 24, 2012, 10:49:59 PM
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.

Title: Re: how to shuffle a set of list ?
Post by: CAB on July 24, 2012, 11:37:41 PM
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.
Title: Re: how to shuffle a set of list ?
Post by: RAIN CODE on July 25, 2012, 01:40:33 AM
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.

Title: Re: how to shuffle a set of list ?
Post by: RAIN CODE on July 25, 2012, 02:09:28 AM
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
Title: Re: how to shuffle a set of list ?
Post by: irneb on July 25, 2012, 03:09:45 AM
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))
Title: Re: how to shuffle a set of list ?
Post by: Stefan on July 25, 2012, 03:10:55 AM
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)
  )
Title: Re: how to shuffle a set of list ?
Post by: irneb on July 25, 2012, 04:29:24 AM
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.
Title: Re: how to shuffle a set of list ?
Post by: irneb on July 25, 2012, 04:50:33 AM
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.
Title: Re: how to shuffle a set of list ?
Post by: Stefan on July 25, 2012, 05:33:25 AM
Quote from: irneb on July 25, 2012, 04:29:24 AM
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.   )

Quote from: irneb on July 25, 2012, 04:50:33 AM
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. _$  
Title: Re: how to shuffle a set of list ?
Post by: irneb on July 25, 2012, 05:44:42 AM
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  :lmao:

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
--------------------------------------------------------------------------------
Title: Re: how to shuffle a set of list ?
Post by: Lee Mac on July 25, 2012, 07:56:45 AM
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
Title: Re: how to shuffle a set of list ?
Post by: irneb on July 25, 2012, 10:05:30 AM
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!
Title: Re: how to shuffle a set of list ?
Post by: Lee Mac on July 25, 2012, 10:23:18 AM
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.
Title: Re: how to shuffle a set of list ?
Post by: irneb on July 25, 2012, 10:40:05 AM
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  ;)
Title: Re: how to shuffle a set of list ?
Post by: highflyingbird on July 25, 2012, 12:44:22 PM
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.  
Title: Re: how to shuffle a set of list ?
Post by: highflyingbird on July 25, 2012, 12:48:36 PM
the length of list is longer,my code runs faster.

On my computer, 20000 items , 10 times test:

HFB:shuffle takes: 1.932 Seconds .
Average performance: 0.1932  Seconds/time.

ShuffleList2  takes: 173.458 Seconds.
Average performance: 17.3458 Seconds/time.

The difference is very huge.

My Big O notation (http://en.wikipedia.org/wiki/Big_O_notation) is O(n),maybe the others is O(n^2).
Title: Re: how to shuffle a set of list ?
Post by: RAIN CODE on July 26, 2012, 12:03:11 AM

You guys are really good. I have still a lot to learn when it come to List.
All the lisps here are shorter than mine. No doubts about it.

I was thinking since my game's lisps are written all in module (subroutines)
Next time I post the game here, maybe someone here could re-write some of the module which I think there are
alot of rooms for improvement. If it shorter I am sure it will run faster.

There are alot of suggestions here dunno which to use  ^-^. All looks so good
Thanks again.
Title: Re: how to shuffle a set of list ?
Post by: highflyingbird on July 26, 2012, 01:29:42 AM
Just a little bit of changed,to simulate the lotto:
Code - Auto/Visual Lisp: [Select]
  1. (defun HFB:GetLottery (MaxNumber Count / i lst array temp Index lastIndex Lottery)
  2.   (setq i MaxNumber)
  3.   (repeat MaxNumber
  4.     (setq lst (cons i lst))
  5.     (setq i (1- i))
  6.   )
  7.  
  8.   (setq LastIndex (1- MaxNumber))
  9.   (setq Array (vlax-safearray-fill (vlax-make-safearray vlax-vblong (cons 0 LastIndex)) lst))
  10.  
  11.   (setq i 0)
  12.   (repeat Count
  13.     (setq Index (LM:RandomRange i LastIndex))
  14.     (setq temp (vlax-safearray-get-element array Index))
  15.     (vlax-safearray-put-element array Index (vlax-safearray-get-element array i))
  16.     (vlax-safearray-put-element array i temp)
  17.     (setq Lottery (cons temp Lottery))
  18.     (setq i (1+ i))
  19.   )
  20.   (reverse Lottery)
  21. )

In China, "double chromosphere":

(cons (LM:randomRange 1 16) (hfb:getlottery 32 6))

(12 17 27 28 32 8 7)

Did you guessed this group numbers? Break your leg! :laugh:
Title: Re: how to shuffle a set of list ?
Post by: irneb on July 26, 2012, 02:57:32 AM
HFB: You're correct! Whenever you use nth on long lists, it's always faster to use an array instead. That's where arrays are better to use than linked-lists (indexing is a simple multiplication instead of an iteration).
Title: Re: how to shuffle a set of list ?
Post by: ElpanovEvgeniy on July 26, 2012, 03:15:36 AM
to solve the problem, really need a full randomization or enough each time to have a different order?

I see the opportunity to multiply to simplify the solution...
Title: Re: how to shuffle a set of list ?
Post by: irneb on July 26, 2012, 06:58:55 AM
Just one thing HFB: Yours would only work if the list contains all the same types. And you'd need to modify the code in order to have a list of different types. Or you could change your function to something like this (hope you don't mind  ;) ):
Code - Auto/Visual Lisp: [Select]
  1. (defun HFB:shuffleTyp  (lst DataType / count array i lastIndex RandNum tmp)
  2.   (setq count (length lst))
  3.   (setq Array (MakeSafeArray (mapcar 'vlax-make-variant lst) DataType)) ;->maybe other type
  4.   (setq i 0)
  5.   (setq LastIndex (1- count))
  6.   (repeat LastIndex
  7.     (setq RandNum (LM:randomrange i LastIndex))
  8.     (setq tmp (vlax-safearray-get-element array RandNum))
  9.     (vlax-safearray-put-element array RandNum (vlax-safearray-get-element array i))
  10.     (vlax-safearray-put-element array i tmp)
  11.     (setq i (1+ i)))
  12.   (vlax-safearray->list array))

Or to have it work exactly as the list-based versions
Code - Auto/Visual Lisp: [Select]
  1. (defun HFB:shuffleVar  (lst / count array i lastIndex RandNum tmp)
  2.   (setq count (length lst))
  3.   (setq Array (MakeSafeArray (mapcar 'vlax-make-variant lst) vlax-vbVariant)) ;->maybe other type
  4.   (setq i 0)
  5.   (setq LastIndex (1- count))
  6.   (repeat LastIndex
  7.     (setq RandNum (LM:randomrange i LastIndex))
  8.     (setq tmp (vlax-safearray-get-element array RandNum))
  9.     (vlax-safearray-put-element array RandNum (vlax-safearray-get-element array i))
  10.     (vlax-safearray-put-element array i tmp)
  11.     (setq i (1+ i)))
  12.   (mapcar 'vlax-variant-value (vlax-safearray->list array)))

An alternative list-based method ... using 6 Packs, then "dealing" each item from the list randomly into one of each pack, and then stacking the packs into one again
Code - Auto/Visual Lisp: [Select]
  1. (defun ShuffleList6  (lst / pac0 pac1 pac2 pac3 pac4 pac5 v)
  2.   (foreach item  lst
  3.     (setq v (read (strcat "pac" (itoa (rem (fix (* (Random nil) 6)) 6)))))
  4.     (set v (cons item (eval v))))
  5.   (append pac0 pac1 pac2 pac3 pac4 pac5))

It's not all that bad compared to the array method for long lists (tested on 20000 integers)
Code: [Select]
Benchmarking ..... done for 8 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(HFB:SHUFFLE LST)                                8      1998      1998     54.15
(HFB:SHUFFLETYP LST vlax-vbLong)                 8      2029      2029     53.33
(HFB:SHUFFLEVAR LST)                             8      2200      2200     49.18
(SHUFFLELIST6 LST)                               4      1278      2556     42.33
(SHUFFLELIST LST)                                1     13525    108200      1.00
--------------------------------------------------------------------------------
And comparing list of 50 items:
Code: [Select]
Benchmarking ............ done for 2048 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(SHUFFLELIST2 LST)                            2048      1263      1263     21.14
(HFB:SHUFFLE LST)                             2048      1436      1436     18.60
(SHUFFLELIST LST)                             2048      1497      1497     17.84
(HFB:SHUFFLETYP LST vlax-vbLong)              2048      1497      1497     17.84
(HFB:SHUFFLEVAR LST)                          2048      1606      1606     16.63
(SHUFFLELIST6 LST)                            2048      1903      1903     14.03
(SHUFFLELIST5 LST)                            1024      1404      2808      9.51
(LM:SHUFFLE LST)                              1024      1436      2872      9.30
(SHUFFLELIST4 LST)                             512      1013      4052      6.59
(SHUFFLELIST3 LST)                             512      1107      4428      6.03
(PH:SHUFFLE1 LST)                              512      1512      6048      4.42
(SHUFFLE LST)                                  128      1669     26704      1.00
--------------------------------------------------------------------------------
Overall, it seems yours is the fastest for a wide range of list lengths. Even the mod to use variants is still faster.