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>