MathGroup Archive 2003

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

Search the Archive

Re: generate random permutation

  • To: mathgroup at smc.vnet.net
  • Subject: [mg40301] Re: generate random permutation
  • From: Bill Rowe <listuser at earthlink.net>
  • Date: Sun, 30 Mar 2003 20:14:22 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

On 3/30/03 at 4:07 AM, r.dorne at ntlworld.com (Umlaut) wrote:

>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).

There are two simple ways to do this in Mathematica either

Permutations[s][[Random[Integer,Length[s!]]

or

<<DiscreteMath`Combinatorica`;
RandomPermutation[s]

I am sure the first method will generate a permutation with the correct probability since it generates all permutations then selects one at random. However, becuase it generates all permutations, it probably isn't the most efficient.

I have not gone through the code used to implement RandomPermutation in the package DiscreteMath`Combinatorica` nor have I run any tests. But assuming it is coded correctly the probability of getting a given permutation should be what you desire.

Finally, Knuth in Vol 3 of Seminumerical Algorithms discusses this problem starting on page 136


  • Prev by Date: Re: Plotting intersections
  • Next by Date: Re: generate random permutation
  • Previous by thread: Re: generate random permutation
  • Next by thread: Re: generate random permutation