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>
- Re: generate random permutation