1
$\begingroup$

Say I have a list that may be out of order.

For instance, the list [1,3,2,4] has 2 and 3 out of place.

This would correspond to a conjugacy class of (2), meaning only one set of 2 elements is out of order (there are six ways to have a conjugacy class of (2)).

My "operation" is selecting three elements randomly, and scrambling them randomly (3! possibilities after selection).

Is there a systematic way to determine how many ways there are to go from a given conjugacy class to all other valid conjugacy classes based on my operation, besides enumerating them all brute-force?

e.g. given the operation, there are X ways to go from conjugacy class Y to conjugacy class Z, etc

A previous question, Linear algebra to find EV of sort algorithm, provides some background on this one.

  • 0
    No worries, the help is still very much appreciated and I now have a much better idea for how to go about tackling this problem. Thank you for all your help2012-03-12

1 Answers 1

3

Depending on what you consider brute force, I don't think you can do a whole lot better than brute force.

I've posted two different Java programs that perform this computation here. One of them simply takes a permutation from each conjugacy class, composes it with all possible scramblings of three elements, and counts the conjugacy classes of the resulting permutations. The other program also performs a lot of computation (in fact it's longer) but does so at a slightly higher level. To understand what it does, think of the cycle structure of a permutation as a set of necklaces. Composing the permutation with a transposition opens two of the necklaces and recombines the ends. If the transposition affects two elements in different cycles, these cycles are combined into one, whereas if it affects two elements in the same cycle, that cycle is split in two. Similarly, composing the permutation with a $3$-cycle opens three of the necklaces and recombines their ends. If the $3$-cycle affects three elements in different cycles, these cycles are combined into one; if it affects two elements in one cycle and a third element in another, part of the first cycle is spliced into the second cycle; and if it affects three elements in the same cycle, that cycle is either just rearranged (if the elements occur in the same order in the cycle and the $3$-cycle) or split in three (if they occur in opposite order). If this seems confusing, try some examples and follow how the cycles are affected by composition with transpositions and $3$-cycles.

The code has a good chance of being correct, as both versions produce the same results.