[GAP Forum] Sampling elements in conjugacy classes of the symmetric group

[John Dixon]

Each conjugacy class of  S_n is determined by the cycle structure of its 
elements. A quick way to find a random cycle structure with probability 
proportional to the size of the corresponding class is as follows.  If 
it is only the cycle structure which you need this is faster than 
finding a random element of  S_n.

    Set m := n and clist := []
    While m > 0 do
       {Choose  k  (uniformly) at random from [1..m]
       Add k to the clist and set m  := m-k}
    return clist

    The resulting clist should be read as a list of cycle lengths.
    [ See Dixon and Mortimer, "Permutation Groups", Springer 1996, 
Exercise 3.6.6.]

       - John Dixon
   

Don King wrote:

> I`d like to sample some elements in a symmetric group of order n based 
> on the ratio of conjugacy classes.
>
> For instance, if a symmetric group just has five conjugacy classes 
> (this is just for illustration, not an actual symmetric group),
>
> Class 1: 10 memeber
> Class2: 20 members
> Class3: 30 memebers
> Class4: 20 members
> Class5: 10 memebers
>
> is it possible to pick random samples like 1,2,3,2,1 elements from 
> each class based on the ratio of each conjugacy classes ?.
>
> Is there any way to pick random samples from each conjugacy class ?.