明らかに，multiset として \(A = B\) が必要なので，以下ではそれを仮定する．
まず簡単のため2-shift で考える． これは常にそろえる事が可能で，先頭から貪欲に決めていけばよい．
次に，3-shift も同様の方針で先頭から揃えてみる． 簡単のため， \(A\) の元は全て異なるとする． 先頭から決めれば，最後の2つ以外は揃う． 最後の2が揃う必要十分条件は， \(A \rightarrow B\) の転倒数が偶数であること．
次に， \(A\) に同じ元があるとする． この場合は転倒数によらず常に揃えられる． 例えば， \(1\) が二つあるときに \(1,1'\) として区別すると， \begin{matrix} B^{0}& :& 2 & 1 & 1'& 3 \\ B^{1}& :& 2 & 1' & 1& 3 \end{matrix} のうち， \(A \rightarrow B^{0}, B^{1}\) のどちらかは偶置換になるから．
メモ
補題: 互換により，サイクルの増加は +1 or -1. とくに，長さ3のperm を施すと，サイクルの増加は +2 or -2 or 0 となるので，偶奇は同じ．
補題: 互換により，サイクルの増加は +1 or -1. とくに，長さ3のperm を施すと，サイクルの増加は +2 or -2 or 0 となるので，偶奇は同じ．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
