generate random permutation

*To*: mathgroup at smc.vnet.net*Subject*: [mg40287] generate random permutation*From*: "Umlaut" <r.dorne at ntlworld.com>*Date*: Sun, 30 Mar 2003 04:07:54 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

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.

**Follow-Ups**:**Re: generate random permutation***From:*Daniel Lichtblau <danl@wolfram.com>