順列全探索がどういうことなのか、やっっっっっと分かったぁー……。分からなすぎて放置してたら1年以上経ってた恐怖。というわけで備忘録。
つまり、C++にあるnext_permutationのようなものを書ければいい。戻り値どうすんの型どうすんのってのは一旦横に置いといて……まず概念の整理から。
よく使われるアルゴリズムの概念を具体的に解説する
順列を全探索するには、昇順に並び替えられた順列を辞書順に次の順列、その次の、……と繰り返し、最終的に降順になるまで並び替えていきます。
例えば
1 2 3 4 5
のような順列があったとすれば、それを
5 4 3 2 1
になるまで並び替えを繰り返すアルゴリズムがあります。
ではこの12345から54321までの間をどうやって列挙するのか。
直感的には末尾にある一番大きい数字の組み合わせの45を入れ替えれば辞書順で次の順列である12354になりますね。では更にその次は？
少し考えると分かるかもしれませんが、この場合は12435になります。
分かっている範囲の順列は下記のようになります。
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
.
.
.
5 4 3 2 1
プログラムを組むのであれば再現性がなくてはなりません。つまり、12345→12354の並び替えと、12354→12435の並び替えで同じ入れ替えの手順を踏む必要があります。ちょっと難しいですね。
順列全探索のアルゴリズム
ということで順列を全探索する際に有名なアルゴリズムを使います。が、私は数学仕草で説明されても8割くらいは分からなかったので、具体的かつ明瞭に。
例えば12354の次の順列を導くとして、
- すぐ右側の数字と比較して「左＜右」の関係にある場所の中で一番右にある場所を覚えます。例の場合、3番目となります。
- 3番目の場所から右側へ3番目の数字より大きい数字のある最も遠い場所も覚えます。優先するのは最も遠いこと。例の場合、5番目となります。
- 覚えた場所の数字同士を入れ替えます。例の場合、12453になります。
- 最初に覚えた3番目の場所より右側の並びを逆順にします。例の場合、12435になります。
これで12354から辞書順で次の順列である12435を得ることができました。
ではこの手順を12345にも適用してみましょう。
- 上記と同様の手順を踏むと、4番目になります。
- 上記と同様の手順を踏むと、5番目になります。
- 入れ替えると、12354になります。
- 4番目よりあとの数字は1つしかないため逆順にしても変化がありません。
はい、これで同じ手順を踏んで次の順列を得ることができました。
これで理解できたと思います。頼む！理解できていてくれ。
だらだらとした補足説明
文字列の並び替えを全探索するというのは、昇順の順列を辞書順に並び替え続けて降順にしていくこと。
あとはこの方法を next_permutation のない C# に実装するだけです。
上記のような手順を踏めば配列の要素が重複していても問題なく次の順列を挙げ続けてくれます。
本記事の下部に実装例を畳んで置いておきますので、できれば自分で実装にチャレンジしてみてください。私もやったんだからさ
概念的な部分の補足。次の順列を得ることを繰り返すのは、末尾から降順にしていくということと同義。入れ替えによって降順にしようとなれば Pi<Pi+1 となる最大の i に注目することは必然で、右側にある大きい数字を左側に入れ替えて持ってくるなら、それより後の並びが降順になっているのも必然でそれを逆順にすれば昇順、つまり辞書順となります。これで次の順列を得られたが、途中から末尾までが昇順となったのであれば、また末尾から降順にするために……と進んでいく。これを全体が降順になるまで行う。
あと筆者が躓いた理由としてはアルゴリズムの解説にある添え字と順列の関係を勘違いしていたこと。このことに気付くまでに1年以上も……苦手意識あるからって逃げすぎだよ……。なんだよちゃんと説明してあるじゃんか、みたいなことを理解してから気付くのが本当に多い。
実装例（C#）
実装例を開く
var next_permutation = (ref int[] p) =>
{
var nxt = (int[])p.Clone();
var l = -1;
var r = -1;
for (int i = p.Length - 2; 0 <= i; i--)
{
if (p[i] < p[i + 1]) { l = i; break; }
}
if (l == -1) { return false; }
for (int i = p.Length - 1; l < i; i--)
{
if (p[l] < p[i]) { r = i; break; }
}
if (r == -1) { return false; }
nxt[l] = p[r];
nxt[r] = p[l];
Array.Reverse(nxt, l + 1, nxt.Length - (l + 1));
p = nxt;
return true;
};
コメント