MathGroup Archive 2003

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

Search the Archive

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.
 
 


  • Prev by Date: Re: Fit with lists instead of functions
  • Next by Date: Re: Need a nice way to do this
  • Previous by thread: Re: Plotting intersections
  • Next by thread: Re: generate random permutation