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