Home » Category » Lisp

Lisp: How Best to Randomize a List?

200| Sun, 27 Apr 2008 22:45:00 GMT| are| Comments (9)
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.

Keywords & Tags: best, randomize, list, lisp

URL: http://programming.itags.org/lisp/155464/
 
«« Prev - Next »» 9 helpful answers below.
are <Proponent...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)

espenvestre | Sun, 27 Apr 2008 22:46:00 GMT |

are <Proponent...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...rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

robwarnock | Sun, 27 Apr 2008 22:47:00 GMT |

P Thu, 09 Aug 2007 11:55:28 +0200, skrev Espen Vestre <espen...vestre.net>:

> are <Proponent...gmx.net> writes:
>
> 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 | Sun, 27 Apr 2008 22:48:00 GMT |

"John Thingstad" <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)

espenvestre | Sun, 27 Apr 2008 22:49:00 GMT |

On Aug 9, 2:45 am, are <Propon......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

scottburson | Sun, 27 Apr 2008 22:50:00 GMT |

On Aug 9, 12:15 pm, Scott Burson <FSet......gmail.com> wrote:
> And this version is fast on both sequences and lists.

I meant, of course, "on both vectors and lists". Sigh...

-- Scott

scottburson | Sun, 27 Apr 2008 22:51:00 GMT |

Scott Burson <FSet.SLB...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

juho_snellman | Sun, 27 Apr 2008 22:52:00 GMT |

On Aug 9, 12:35 pm, Juho Snellman <jsn......iki.fi> wrote:
> Scott Burson <FSet......gmail.com> wrote:
>
> 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

scottburson | Sun, 27 Apr 2008 22:53:00 GMT |

On Aug 9, 5:45 am, are <Propon......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.

gene | Sun, 27 Apr 2008 22:54:00 GMT |

Lisp Hot Answers

Lisp New questions

Lisp Related Categories