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
- References:
- generate random permutation
- From: "Umlaut" <r.dorne@ntlworld.com>
- generate random permutation