maradonah's blog

By maradonah, history, 4 years ago, In English,

I participated in the codeforces educational round 4 and I liked problem E (Square Root of Permutation) that involves finding square root of a given permutation. The solution requires representing the permutation as a graph then decomposing this graph into cycles. Checking certain properties of these cycles such as the number of even cycles with the same length is the key point to finding a solution.

The idea of considering a permutation as a graph and mapping operations on the permutation to operations in the corresponding graph is very new and interesting to me. I tried to search in Google and Codeforces about other problems and explanations related to this concept but I was not able to find relevant stuff other than: Wikipedia article and a codechef problem. I wonder whether you can share some resources about this topic that you might have met during practice or suggest better keywords for finding relevant resources.

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

The idea of decomposing a permutation into disjoint cycles comes from group theory. You may learn more about this topic by studying group theory and abstract algebra (more specifically, symmetric groups https://en.wikipedia.org/wiki/Symmetric_group ). In the past all the groups that were studied were considered to be a subgroup of some symmetric group. Later another more abstract definition of a group was given and proved to be equivalent.

I like the textbook "Modern Algebra" by Dummit and Foote on this topic, but other better resources may exist.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Here is an excellent explanation of the cycle notation for permutations: http://people.math.sfu.ca/~jtmulhol/math302/notes/4-Permutations-CycleForm.pdf

Here is an interactive website on permutations and cycles: http://nrich.maths.org/2789 . I found this one particularly fun since it illustrates permutations and cycles in an intuitive way.