MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: generate random permutation

  • To: mathgroup at smc.vnet.net
  • Subject: [mg40304] Re: [mg40287] generate random permutation
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Sun, 30 Mar 2003 20:14:34 -0500 (EST)
  • References: <200303300907.EAA16152@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Umlaut wrote:
> 
> I am a researcher in Artificial Intelligence and I have a question about
> generating random
> permutation of a set of numbers.
> 
> More formal definition:
> Given a set of N numbers S = {n1, ., nn}
> 
> how to efficiently and accurately generate P(S) = random_permutation(S)
> Ex: S = {3,4,12}, P(S) should have a probability equals to 1/3! = 1/6 to
> return
> one of the following permutations:
> {(3,4,12)(3,12,4)(4,3,12)(4,12,3)(12,3,4)(12,4,3)}
> and a complexity equals to O(N).
> 
> and
> 
> how to efficiently generate an iterator on the numbers which will be
> returned by P(S) ?
> Ex: S = {3,4,12} P(S) can return any of the permutations described
> below, but
> what we want here is to get an iterator on the future numbers without
> creating the full permutation
> 
> 
> Do you know any algorithm performing this task which is very efficient
> in terms of quality (each permutation
> has the same probability to be generated) and in terms of complexity
> (minimal number of operations
> is necessary to perform this operation n2, n, log n, etc.).
> 
> If you have any clue or web links where I can find this information,
> this would be very much appreciated.
> 

Below are two links to responses in MathGroup to similar questions in
the past.

http://forums.wolfram.com/mathgroup/archive/2001/Jan/msg00087.html

http://forums.wolfram.com/mathgroup/archive/2001/Apr/msg00263.html

If you search the MathGroup archives for "random permutation" I think
you will find several other past posts of relevance.


Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: generate random permutation
  • Next by Date: Re: Need a nice way to do the "left count"
  • Previous by thread: generate random permutation
  • Next by thread: Re: generate random permutation