Permutation Cycle Decomposition Calculator
Permutation Cycle Decomposition Calculator computes the cycle decomposition of a permutation on \\( n \\) elements. Enter a permutation as a sequence of numbers (e.g., 2,3,1,5,4) to find its cycles and visualize it as a directed graph.
A permutation on \\( n \\) elements maps each integer \\( \{1, 2, \ldots, n\} \\) to another. The cycle decomposition represents the permutation as disjoint cycles, where each cycle shows the sequence of mappings (e.g., \\( 1 \to 2 \to 3 \to 1 \\)).
Algorithm Steps:
1. Read the permutation as a sequence \\( \sigma(1), \sigma(2), \ldots, \sigma(n) \\).
2. Initialize an empty list of cycles and a set of unvisited elements.
3. For each unvisited element, follow the permutation to build a cycle until returning to the starting element.
4. Mark elements as visited and continue until all elements are included.
5. Output the cycles and visualize as a directed graph.
Mathematical Formulation:
\\[ \text{For permutation } \sigma: \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}, \\] \\[ \text{For each unvisited } i: \\] \\[ \text{Cycle} = (i, \sigma(i), \sigma^2(i), \ldots) \text{ until } \sigma^k(i) = i \\]Example Calculation
Sample Input
Permutation: \\( 2, 3, 1, 5, 4 \\)
Step 1: Start with \\( 1 \\), \\( \sigma(1) = 2 \\), \\( \sigma(2) = 3 \\), \\( \sigma(3) = 1 \\):
\\[ \text{Cycle: } (1, 2, 3) \\]Step 2: Next unvisited is \\( 4 \\), \\( \sigma(4) = 5 \\), \\( \sigma(5) = 4 \\):
\\[ \text{Cycle: } (4, 5) \\]Result: Cycle Decomposition: \\( (1, 2, 3)(4, 5) \\)