Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I am sorry to tell you that, you need to read upon the groups, and understand the terms you're using. For answerers, you'll find this and this useful. The OP does not understand what groups are, in an axiomatic fashion. I don't see any reasonable way, one can write an answer. –  user21436 Mar 11 '12 at 5:28
    
Can you explain what you write in the third patch of your question? What does conjugacy class of $(2)$ mean? –  user21436 Mar 11 '12 at 5:28
    
As I reread the question, conjugacy class is used in an entirely different sense, and the last question can be answered in a similar fashion joriki answered one of your previous questions. –  user21436 Mar 11 '12 at 5:54
    
I explained what I meant in the OP by (2). It's also the same sort of thing explained in en.wikipedia.org/wiki/Conjugacy_class#Examples (2) just means a scenario where a swapping of 2 is sufficient to sort the list. Something like (3) would mean 3 are out of place. (2)(2) means two sets could be switched (e.g. [2,1,4,3]). –  John Smith Mar 11 '12 at 6:13
    
Oh, well, I am not sure if that is standard, but for the love of god, please take a book on group theory and go through the details of what group actions are, what is conjugacy? And, then, you'll see a connection via the action of $S_3$ on the set of its own conjugacy classes. –  user21436 Mar 11 '12 at 6:21

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.