3
$\begingroup$

Consider the set $1, 2, \dots, N$, where $N>1$ is a natural number. In general, there are $N!$ permutations of this list. Let $\sigma$ be one such permutation. We define the tuple $\varphi(\sigma) = \left (c_1,\dots,c_N \right)$, where $c_i$ is the number of cycles of length $i$ in $\sigma$. This tuple is sometimes referred to as the cycle type of a permutation. The degeneracy of the cycle type is the number of permutations that are mapped by $\varphi$ to the same cycle type.

For example, if $N=3$, we have $6$ possible permutations, but some of these permutations are mapped by $\varphi$ to the same tuple:

$$ \begin{align} 123 & =\left(1\right)\left(2\right)\left(3\right)\to\varphi=\left(3,0,0\right)\\\\ 312 & =\left(132\right)\to\varphi=\left(0,0,1\right)\\\\ 231 & =\left(123\right)\to\varphi=\left(0,0,1\right)\\\\ 213 & =\left(12\right)\left(3\right)\to\varphi=\left(1,1,0\right)\\\\ 132 & =\left(1\right)\left(23\right)\to\varphi=\left(1,1,0\right)\\\\ 321 & =\left(13\right)\left(2\right)\to\varphi=\left(1,1,0\right) \end{align} $$

Clearly, there is just one permutation (the identity permutation) with the cycle structure $\left(3,0,0\right)$, i.e., a permutation having $3$ trivial cycles of length $1$ and no cycles longer than that. Also, there are $3$ permutations that have the same cycle structure of $\left(1,1,0\right)$, i.e., permutations with $1$ cycle of length $1$ and $1$ cycle of length $2$. Finally, there are two permutations with the cycle structure $\left(0,0,1\right)$, i.e., permutations with $1$ cycle of length $3$.

Is there an efficient algorithm for generating all the unique cycle types and their degeneracies for a given $N$ without explicitly enumerating all the $N!$ permutations? Perhaps a recursive algorithm that constructs new cycles types based on previous ones?

$\endgroup$

2 Answers 2

1
$\begingroup$

There is one cycle type per integer partition of $N$. So you can enumerate all the cycle types by any standard algorithm to enumerate the integer partitions of $N$.

The cycle index is a multivariate polynomial, with one monomial per cycle type, and the coefficient of that monomial is the degeneracy of the corresponding cycle type. So you can read off the information you want from the cycle index.

You can compute the cycle index for these $N!$ permutations via a recursive formula given at https://en.wikipedia.org/wiki/Cycle_index#Symmetric_group_Sn, namely,

$$Z_N(x_1,\dots,x_N) = \frac{1}{N} \sum_{t=1}^N x_t Z_{N-t}(x_1,\dots,x_{n-t}).$$

The coefficient of $x_1^{i_1} \cdots x_n^{i_n}$ in $Z_n$ is $1/N!$ times the degeneracy of cycle type $(i_1,\dots,i_n)$.

$\endgroup$
2
  • $\begingroup$ Thank you. Am I correct in assessing the complexity of the recursive algorithm to be $N^2$? My reasoning is that one must evaluate $N$ terms in the list $Z_1, \dots, Z_N$, and in order to calculate $Z_m$ one needs to evaluate $m$ monomials of the form $x_t$. So assuming the evaluation of the latter is $\mathcal{O}(1)$, we have an overall complexity of $\mathcal{O}(N^2)$. $\endgroup$
    – user187240
    Commented Apr 22 at 8:23
  • $\begingroup$ @user187240, I expect it's much worse than that. The time to evaluate $x_t Z_{N-t}(x_1,\dots,x_{n-t})$ is proportional to the number of monomials in $Z_{N-t}(x_1,\dots,x_{n-t})$, which I think grows subexponentially fast. So I expect this will take subexponential time. Please confirm my reasoning and also my claims about how to compute the cycle index. I haven't verified them -- I have just copied from what I read in Wikipedia, so it'll be important for you to dive into it and check it carefully. $\endgroup$
    – D.W.
    Commented Apr 22 at 16:47
0
$\begingroup$

Here's an idea. I tested it with $N=4$ from $N=3$ and I think it works for any $N$, but I am not sure my explanation is very rigorous.

Starting from a permutation $\sigma\in \mathfrak{S}_N$, you can construct a permutation $\sigma'\in \mathfrak{S}_{N+1}$ by:

  • either considering $\sigma'(N+1) = N+1$ and $\sigma'(k) = \sigma(k)$ for $k\leqslant N$;
  • or "inserting" $N+1$ in the middle of a cycle of $\sigma$, for which the number of different possible insertions is the size of the cycle.

What that means is that a cycle type $(c_1, …, c_N)$ of weight $w$ of $\mathfrak{S}_N$ will contribute to:

  • the cycle type $(c_1+1, c_2, …, c_N, 0)$, with weight $w$;
  • for all $i\in \{1, …, N\}$, the cycle type $(c_1, …, c_{i-1}, c_i - 1, c_{i+1}+1, c_{i+2}, …)$, with weight: $$w\times c_i \times i$$ In the previous product, the factor $c_i$ represents the number of cycles from which to choose the insertion, and the factor $i$ is the number of possibilities of insertions.

As an example, cycles types of $\mathfrak{S}_4$ can be constructed from cycles types of $\mathfrak{S}_3$:

  • $(3, 0, 0)$ of weight $1$ contributes to:
    • $(4, 0, 0, 0)$ with weight $1$;
    • $(2, 1, 0, 0)$ with weight $3$;
  • $(1, 1, 0)$ of weight $3$ contributes to:
    • $(2, 1, 0, 0)$ with weight $3$;
    • $(0, 2, 0, 0)$ with weight $3\times 1 = 3$;
    • $(1, 0, 1, 0)$ with weight $3\times 2 = 6$;
  • $(0, 0, 1)$ of weight $2$ contributes to:
    • $(1, 0, 1, 0)$ with weight $2$;
    • $(0, 0, 0, 1)$ with weight $2\times 3 = 6$.

Finally, we have:

  • $(4,0,0,0)$: $1$
  • $(2, 1, 0,0)$: $6$
  • $(1,0,1,0)$: $8$
  • $(0,2,0,0)$: $3$
  • $(0,0,0,1)$: $6$.
$\endgroup$
1
  • $\begingroup$ Thank you. I implemented this algorithm in Python and it seems to be working for all $N$. However, it still scales factorially with $N$. $\endgroup$
    – user187240
    Commented Apr 22 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.