       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