順列全探索がどういうことなのか、やっっっっっと分かったぁー……。分からなすぎて放置してたら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つしかないため逆順にしても変化がありません。
はい、これで同じ手順を踏んで次の順列を得ることができました。
これで理解できたと思います。頼む！理解できていてくれ。
入れ替えるのは数値ですが、逆順にするために覚えておくのは配列の添字（番目）のほうです。（１敗）
具体的に実装するもの
- 入れ替える左側を見つける。
- 入れ替える右側を見つける。
- 入れ替える。
- 入れ替えた左側の位置よりも右側の配列（L<iを満たす全てのi）を逆順にする。
補足説明
文字列の並び替えを全探索するというのは、昇順の順列を辞書順に並び替え続けて降順にしていくこと。
上記のような手順を踏めば配列の要素が重複していても問題なく次の順列を挙げ続けてくれます。
本記事の下部に実装例を畳んで置いておきますので、できれば自分で実装にチャレンジしてみてください。私もやったんだからさ
（分かり辛かったので説明を少し修正）概念的な部分の補足。次の順列を得ることを繰り返すのは、末尾から降順にしていくということと同義。入れ替えによって降順にしようとなれば左手には Pi<Pi+1 とを満たす最大の i に注目するのは必然、右手もPi<Pjを満たす最大のjに注目することは必然で、右側にある大きい数字を左側に入れ替えて持ってくるなら、それより後の並びが降順になっているのも必然。（上の例でいう12453の53がそれ）
その並びを逆順にすれば昇順になる。つまり、そこまでやってようやく全体が辞書順の次となっている配列が出来上がるわけです。
これで次の順列を得られたが、途中から末尾までが昇順となったのであれば、また末尾から降順にするために……と進んでいく。これを全体が降順になるまで行う。
まだ俺の解説フェイズは終了してないぜ！
あとはこれを next_permutation のない C# に実装するだけ……しかし、本当にそうでしょうか？
記事の最初で一旦横に置いてた「戻り値どうすんの？」という疑問にここで直面します。
C#にはC++とは違う仕様があるため、メソッドの利用法（変数の扱い）にも気を配る必要があります。特にこの順列全探索では普段から普通に実装するメソッドとは違って戻り値が複数あり、それがそもそも配列であり、それぞれの戻り値が判明した時点でreturnして別の処理を挟む必要も出てくるため、プログラミング初学者にとっては鬼門です。（３６５敗）
解決法は以下が挙げられます。
- refキーワードを使う（C++での用法に近く実装上簡便）
- 戻り値にタプルを使う。
- 呼び出す人の責任として考える。
refキーワードを使う
引数を配列、戻り値をbool値で配列が有効かどうかを返します。
C++のnext_permutationで想定されている処理に近い実装になり、そのおかげで公式解説の処理をC#に落とし込みやすく便利です。
C#の標準ライブラリでも見られるQueue.TryDequeue()などこのタイプの実装が存在する通り、while文が書きやすくなります。
実際にはrefキーワードを使わなくても配列のインスタンスは参照渡しのため同様の処理は実装できますが、メソッドを利用する立場になるとrefキーワードがあることによって「渡した変数をもう一回使うメソッド」であること、「渡した変数に対してメソッド内で変更が加わる（＝副作用がある）」ということが伝わるため、メソッドを利用する上で具体的な実装まで見る必要なくなります。
未来の自分がそれら具体的な実装を忘れてもメソッドの意味と利用法さえ分かれば処理に組み込める点で有利です。
見慣れないものを使うということで不安になる気持ちは分かりますが（２敗）、変数を監視しながら変更を加え適宜returnする必要があるこの状況では、refがほとんどの場合で最適解と思われます。
戻り値にタプルを使う
refキーワードを使えない環境にある場合の選択肢。
タプルを簡単に言うと変数2つを1つとして合体できるものです。(a, b)のような形になります。
「この戻り値が有効かどうか」と「結果」の変数を合体させ、これを戻り値として返します。
難点はwhileの実装が少し面倒になること。とはいえあまり変わりませんが、refキーワードが簡便でC#の標準ライブラリでも採用される設計の実装になるため、そちらをおすすめします。
呼び出す人の責任として考える。
通常通りのメソッドとして実装。引数をメソッド内で処理した後で戻り値として投げ返し、その戻り値が有効かどうかもメソッド外で判断する実装。
基本はなしの選択です。refキーワードの有り難さを噛み締めたい人向け。
終わり
ここまでの解説で実装できるはずです。どうしても分からなければ実装例（ほぼ答え）も下にあるのでどうぞ。
おまけ
筆者が躓いた理由としてはアルゴリズムの解説にある添え字と順列の関係を勘違いしていたこと。このことに気付くまでに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;
};
コメント