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 ). 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:

Here is an interactive website on permutations and cycles: . I found this one particularly fun since it illustrates permutations and cycles in an intuitive way.