The old Google Groups will be going away soon, but your browser is incompatible with the new version.
permuting a list
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 2 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Feb 17 2009, 11:56 am
From: "Okasaki, C. DR EECS" <Christopher.Okas...@usma.edu>
Date: Tue, 17 Feb 2009 11:56:02 -0500
Local: Tues, Feb 17 2009 11:56 am
Subject: [Haskell-cafe] Re: permuting a list

The discussion of randomly permuting a list comes up every few years.
Here's
what I wrote last time (2005):

"Clearly, you can do a perfect shuffle in O(N) time using mutable
arrays,
using the standard imperative algorithm.  You can also do it in O(N)
expected time using *immutable* arrays, using Haskell's bulk array
operations.

1. Start with a list of length N.  If N < 2, stop.
2. Pair each element with a random index in the range [1,2N] (or
[0,2N-1]).
3. Use "accum" to create an array of size 2N, where slot I contains a
list of all the elements paired with I.
4. Map the shuffle function recursively across the array to re-shuffle
any slots that got more than one element.
5. Append all the slots together into the result list.

If you leave out step 4, you get an algorithm that runs in O(N)
worst-case time, rather than expected time, but you no longer have a
perfect shuffle (although it might be good enough).  Upping the size of
the array from 2N to 3N or 4N will help reduce collisions, but will not
entirely eliminate them.

With step 4, you can imagine pathological cases where everything gets
put in the same slot, but with a reasonable random number generator, it
is vanishingly unlikely that you will have enough collisions to drive
the cost higher than linear.  Again, upping the size of the array from
2N to 3N or 4N makes this even more unlikely."

Now, you can consider it cheating to say this is O(N) expected time
because it uses O(N log N) random bits.  Fair enough.  It is O(N) to the
same extent that the ordinary imperative algorithm is O(N), albeit
expected
rather than worst case.

-- Chris

_______________________________________________

To post a message you must first join this group.
You do not have the permission required to post.
More options Feb 18 2009, 6:25 pm
From: Henning Thielemann <lemm...@henning-thielemann.de>
Date: Thu, 19 Feb 2009 00:25:55 +0100 (CET)
Local: Wed, Feb 18 2009 6:25 pm
Subject: [Haskell-cafe] Re: permuting a list

On Tue, 17 Feb 2009, Okasaki, C. DR   EECS wrote:

> The discussion of randomly permuting a list comes up every few years.  Here’s
> what I wrote last time (2005):

... How about putting it on the Wiki?

_______________________________________________