What's a good way to randomize a list? When I needed to do this
recently, I resorted to CONSing each list element with a random
number, sorting by the random numbers and then stripping them back
out. This works, but doing a sort when all I need is randomization is
obviously highly inefficient.
are <·········@gmx.net> wrote:
+---------------
| What's a good way to randomize a list? When I needed to do this
| recently, I resorted to CONSing each list element with a random
| number, sorting by the random numbers and then stripping them back
| out. This works, but doing a sort when all I need is randomization is
| obviously highly inefficient.
+---------------
I'm not sure what's so "obviously highly inefficient" about a SORT,
since generating the number of good-quality random numbers you will
need for decent randomization is going to be *much* more expensive
than a simple SORT at the end. But if you don't like your method,
then try this:
(coerce (random-shuffle (coerce your-list 'vector)) 'list))
See the Google Groups archive for ways to implement RANDOM-SHUFFLE
in Common Lisp. [Hint: "Fisher-Yates"...]
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
are <·········@gmx.net> writes:
> What's a good way to randomize a list?
Knuths shuffle algorithm.
(defun shuffle (seq)
(let ((n (length seq)))
(dotimes (i n seq)
(rotatef (elt seq i)(elt seq (+ i (random (- n i))))))))
Note that this implementation work on any SEQUENCE type, not only
lists.
--
(espen)
P� Thu, 09 Aug 2007 11:55:28 +0200, skrev Espen Vestre <·····@vestre.net>:
> are <·········@gmx.net> writes:
>
>> What's a good way to randomize a list?
>
> Knuths shuffle algorithm.
>
> (defun shuffle (seq)
> (let ((n (length seq)))
> (dotimes (i n seq)
> (rotatef (elt seq i)(elt seq (+ i (random (- n i))))))))
>
> Note that this implementation work on any SEQUENCE type, not only
> lists.
For better efficieny you might want to use aref for a array or nth for a
list.
Saves you the dispatch time of elt.
"John Thingstad" <··············@chello.no> writes:
> For better efficieny you might want to use aref for a array or nth for
> a list.
> Saves you the dispatch time of elt.
Sure, if you need the extra speed, the dispatch time is actually quite
significant. But if you're shuffling a lot of long lists, it's much
more important to use an array while shuffling!
E.g.
(coerce (shuffle (coerce x 'simple-vector)) 'list)
takes only a few milliseconds on my machine (with a 20000 element X)
while using a LIST-specialized version directly on X takes several
seconds.
--
(espen)
On Aug 9, 2:45 am, are <·········@gmx.net> wrote:
> What's a good way to randomize a list? When I needed to do this
> recently, I resorted to CONSing each list element with a random
> number, sorting by the random numbers and then stripping them back
> out. This works, but doing a sort when all I need is randomization is
> obviously highly inefficient.
Here's what I would do -- simple and efficient.
(defun shuffle (seq)
(sort seq (lambda (x y)
(declare (ignore x y))
(= 0 (random 2)))))
As others have pointed out, `sort' is more efficient than you think.
It's all that consing that's inefficient.
And this version is fast on both sequences and lists.
The amusing thing about this is that it's the very fact that `sort' is
O(n log n) that makes it work. It wouldn't work with bubble sort --
the poor thing would terminate only by accident. It's precisely the
fact that the more sophisticated sort algorithms are careful to do
only the minimum number of comparisons, under the assumption that the
predicate is consistent, that makes them do what we want given this
inconsistent predicate.
-- Scott
On Aug 9, 12:15 pm, Scott Burson <········@gmail.com> wrote:
> And this version is fast on both sequences and lists.
I meant, of course, "on both vectors and lists". Sigh...
-- Scott
Scott Burson <········@gmail.com> wrote:
> (defun shuffle (seq)
> (sort seq (lambda (x y)
> (declare (ignore x y))
> (= 0 (random 2)))))
>
> The amusing thing about this is that it's the very fact that `sort' is
> O(n log n) that makes it work. It wouldn't work with bubble sort --
> the poor thing would terminate only by accident. It's precisely the
> fact that the more sophisticated sort algorithms are careful to do
> only the minimum number of comparisons, under the assumption that the
> predicate is consistent, that makes them do what we want given this
> inconsistent predicate.
Sure, it will terminate (this is actually required by the standard).
But it doesn't do what is wanted; there's no reason to assume that the
result of sorting a sequence by a random predicate will produce all
permutations of the sequence with even remotely the same
probabilities.
--
Juho Snellman
On Aug 9, 12:35 pm, Juho Snellman <······@iki.fi> wrote:
> Scott Burson <········@gmail.com> wrote:
> > (defun shuffle (seq)
> > (sort seq (lambda (x y)
> > (declare (ignore x y))
> > (= 0 (random 2)))))
>
> > The amusing thing about this is that it's the very fact that `sort' is
> > O(n log n) that makes it work. It wouldn't work with bubble sort --
> > the poor thing would terminate only by accident. It's precisely the
> > fact that the more sophisticated sort algorithms are careful to do
> > only the minimum number of comparisons, under the assumption that the
> > predicate is consistent, that makes them do what we want given this
> > inconsistent predicate.
>
> But it doesn't do what is wanted; there's no reason to assume that the
> result of sorting a sequence by a random predicate will produce all
> permutations of the sequence with even remotely the same
> probabilities.
Whoops, you're right. It works for sequences whose length is a power
of 2, but otherwise fails to be uniform. My bad.
Still, if all I wanted was something quick and dirty, I might use it.
Depends on the situation.
-- Scott
On Aug 9, 5:45 am, are <·········@gmx.net> wrote:
> What's a good way to randomize a list? When I needed to do this
> recently, I resorted to CONSing each list element with a random
> number, sorting by the random numbers and then stripping them back
> out. This works, but doing a sort when all I need is randomization is
> obviously highly inefficient.
It happens I worked out an algorithm to do this about 15 years ago.
Here's a reference, which includes a Clisp function code of 10 lines
or so. It ran considerably faster than the sort in LCL of that time.
@article{144238,
author = {Eugene K. Ressler},
title = {Random list permutations in place},
journal = {Inf. Process. Lett.},
volume = {43},
number = {5},
year = {1992},
issn = {0020-0190},
pages = {271--275},
doi = {http://dx.doi.org/10.1016/0020-0190(92)90222-H},
publisher = {Elsevier North-Holland, Inc.},
address = {Amsterdam, The Netherlands, The Netherlands},
}
If you don't have access to this, write me and I will dig out the
source.
But note that if you randomly permute a list of conses by setf'ing
pointers (which is what the algorithm above does), you end up with a
data structure that has terrible cache/paging properties for
traversal.
Hi,
I don't know how or whether this would help you -
I've been working on an audio selection sequencer (written in
Nyquist [based on XLISP] for the open source sound editor Audacity
http://audacity.sourceforge.net ), and wrote the following to
randomize the list of up to 96 notes programmed by the user:
; function to rotate a list:
; (my-rotate (list 0 1 2 3 4 5)) -> (1 2 3 4 5 0)
; (my-rotate (list 0 1 2 3 4 5) 2) -> (2 3 4 5 0 1)
(defun my-rotate (list &optional (n 1))
(if (<= n 0)
list
(my-rotate (append (last list) (reverse (cdr (reverse list)))) (1- n))))
; function to randomize a list
(defun randomize-list (list)
(setf temp-list nil)
(dotimes (i (length list))
(setf list (my-rotate list (random (length list))))
(setf temp-list (push (car list) temp-list))
(pop list))
temp-list)
David
--
David R. Sky
http://www.shellworld.net/~davidsky/
On Thu, 9 Aug 2007, are wrote:
> What's a good way to randomize a list? When I needed to do this
> recently, I resorted to CONSing each list element with a random
> number, sorting by the random numbers and then stripping them back
> out. This works, but doing a sort when all I need is randomization is
> obviously highly inefficient.
>
>
"David R. Sky" <···@viper.wapvi.bc.ca> writes:
> Hi,
>
> I don't know how or whether this would help you -
>
> I've been working on an audio selection sequencer (written in
> Nyquist [based on XLISP] for the open source sound editor Audacity
> http://audacity.sourceforge.net ), and wrote the following to
> randomize the list of up to 96 notes programmed by the user:
>
> ; function to rotate a list:
> ; (my-rotate (list 0 1 2 3 4 5)) -> (1 2 3 4 5 0)
> ; (my-rotate (list 0 1 2 3 4 5) 2) -> (2 3 4 5 0 1)
> (defun my-rotate (list &optional (n 1))
> (if (<= n 0) list
> (my-rotate (append (last list) (reverse (cdr (reverse list)))) (1- n))))
>
>
> ; function to randomize a list
> (defun randomize-list (list)
> (setf temp-list nil)
> (dotimes (i (length list))
> (setf list (my-rotate list (random (length list))))
> (setf temp-list (push (car list) temp-list))
> (pop list))
> temp-list)
Hi David,
Read this thread:
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/d59b4ef3886b02e3
Tamas
Tamas Papp <······@gmail.com> writes:
> "David R. Sky" <···@viper.wapvi.bc.ca> writes:
>
>> Hi,
>>
>> I don't know how or whether this would help you -
>>
>> I've been working on an audio selection sequencer (written in
>> Nyquist [based on XLISP] for the open source sound editor Audacity
>> http://audacity.sourceforge.net ), and wrote the following to
>> randomize the list of up to 96 notes programmed by the user:
>>
>> ; function to rotate a list:
>> ; (my-rotate (list 0 1 2 3 4 5)) -> (1 2 3 4 5 0)
>> ; (my-rotate (list 0 1 2 3 4 5) 2) -> (2 3 4 5 0 1)
>> (defun my-rotate (list &optional (n 1))
>> (if (<= n 0) list
>> (my-rotate (append (last list) (reverse (cdr (reverse list)))) (1- n))))
>>
>>
>> ; function to randomize a list
>> (defun randomize-list (list)
>> (setf temp-list nil)
>> (dotimes (i (length list))
>> (setf list (my-rotate list (random (length list))))
>> (setf temp-list (push (car list) temp-list))
>> (pop list))
>> temp-list)
>
> Hi David,
>
> Read this thread:
>
> http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/d59b4ef3886b02e3
Sorry David, I missed the fact that you are not the OP. The answer
was addressed to the OP.
Tamas
Hi Tamas,
What's 'op'? - "original poster"?
Thanks for the link anyways, there's alway sroom for more learning! And many
XLISP functions in Audacity Nyquist are still unbound or do not work
properly, so we sometimes have to write our own.
Also, because much of my own Nyquist coding has been self-learned, I think
some of my code is less-than-optimal.
*grin*
David
--
David R. Sky
http://www.shellworld.net/~davidsky/
On Thu, 23 Aug 2007, Tamas Papp wrote:
> Tamas Papp <······@gmail.com> writes:
>
>> Hi David,
>>
>> Read this thread:
>>
>> http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/d59b4ef3886b02e3
>
> Sorry David, I missed the fact that you are not the OP. The answer
> was addressed to the OP.
>
> Tamas
>
"David R. Sky" <···@viper.wapvi.bc.ca> writes:
> Hi Tamas,
>
> What's 'op'? - "original poster"?
yes
> Thanks for the link anyways, there's alway sroom for more learning!
> And many XLISP functions in Audacity Nyquist are still unbound or do
> not work properly, so we sometimes have to write our own.
>
> Also, because much of my own Nyquist coding has been self-learned, I
> think some of my code is less-than-optimal.
Same applies to me. I mean to read some good book about algorithms,
at least to know where to look them up.
Tamas