MathGroup Archive 2003

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

Search the Archive

generate random permutation

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

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
one of the following permutations:
and a complexity equals to O(N).
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