By maradonah, history, 5 years ago,

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.

• +11

 » 5 years ago, # | ← Rev. 3 →   0 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.
 » 5 years ago, # |   +1 Here is an excellent explanation of the cycle notation for permutations: http://people.math.sfu.ca/~jtmulhol/math302/notes/4-Permutations-CycleForm.pdfHere 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.