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