N(1) N(2) N(n) p(X ,X ,... ,X ) = X + X + .... + X 1 2 n 1 2 nis called the cycle structure representation (CSR) of a. All permutations of [4] with CSR
2 1 0 0 p(X ,X ,X ,X ) = X + X + X + X 1 2 3 4 1 2 3 4are as follows:
One-Line Notation |
Cycle Notation |
---|---|
1 2 4 3 | (1)(2)(34) |
1 4 3 2 | (1)(24)(3) |
4 2 3 1 | (14)(2)(3) |
1 3 2 4 | (1)(23)(4) |
3 2 1 4 | (13)(2)(4) |
2 1 3 4 | (12)(3)(4) |
The cycle structure representation of permutations is commonly used in Polya-Burnside theory of counting.
The algorithm used is from the paper: U. Taylor and F. Ruskey, Fast Generation of Restricted Classes of Permutations, Manuscript 1995.