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) \)