(より詳しい解説は後日ブログで公開します)

\(N \ge 3\) とします．\(\mathfrak{S}_N\) が \(2\) 元 \(r = (2, 3, \ldots, N, 1)\) と \(s = (2, 1, 3, \ldots, N)\) で生成されることを用います (すべての順列は隣接 swap だけで作れますが，全体のシフトがあれば隣接 swap は特定の箇所でできればよいです)．

\(r, s\) に該当する元を全探索し，入力のかけ算表に従って実際に \(N!\) 個の元を生成し，正しいかをチェックする，という方法で \(N!\) について多項式時間で解けます．これを高速化します．

試すべき \(r, s\) の候補を減らすには，位数を見るのが簡単です．例えば \(N = 6\) のとき，位数 \(N\) の元は \(240\) 個，位数 \(2\) の元は \(75\) 個です．共役類の大きさを見ることでもう少し絞ることもできます．

\(N!\) 個の元を生成する部分は，木構造をあらかじめ計算しておけば \(O(N!)\) 時間でできます．例えば，各 \(2 \le i \le N!\) に対し \(P[i] = P[j] \circ (1, \ldots, k-1, k+1, k, k+2, \ldots, N)\) なる \(j, k\) を求めておき，\((1, \ldots, k-1, k+1, k, k+2, \ldots, N) = r^{k-1} s r^{-(k-1)}\) を用いればよいです．

\(N!\) 個の相異なる元が生成できたのちに正しいかチェックする部分は，\((N!)^2\) 組すべてを試すのではなく，片方が \(r, s\) のいずれかである場合のみを確認すればよいです (入力が群のかけ算表であることを用いています)．実は，かけ算表のチェックを丸ごと飛ばすこともできます．

なお，答えの個数は \(\mathfrak{S}_N\) の自己同型の個数に等しいです．これは \(N = 2\) のとき \(1\)，\(N = 6\) のとき \(2 \cdot 6!\)，\(N \ne 2, 6\) のとき \(N!\) であることが知られています．\(N = 6\) のときは \(r, s\) に対応しうる共役類が複数あるなど特殊な場合になっているので注意してください．