概要
next_permutationというアルゴリズムが実装を眺めてもよくわからなかったので自分がわかるようにまとめてみました。
C++で書いてます。
参考にしたもの
C++日本語リファレンス std::next_permutation
そもそもnext_permutationって何？
順列生成アルゴリズム。
辞書順で次の数列を生成出来る。
実際に、数列を生成してみる。
#include <iostream>
#include <algorithm>
int main() {
int array[] = {1, 2, 3};
do {
for (int i = 0; i < 3; i++) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}while (std::next_permutation(array, array + 3));
}
結果
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
順列が生成されていることが確認できる。辞書順。
どのように実装されているのか？
実装例を見てもイテレータがインクリメント/デクリメントを繰り返しててイマイチ自分には読みにくい。
ので一旦条件を簡単にする。
前提条件
- 要素の数は2以上
- 要素は整数(本来は<演算子が使えればなんでもいい)
- 予めソート済み
ということで考えていきます。
辞書順で次の数列をどうやってつくるのか
結論から言えば、
配列arrayのインデックスi, jを、
iはarray[l] < array[l+1]を満たすlのうち最大のもの
jは末尾から探索して初めて現れるarray[i]より大きい要素のインデックス
としたときに、
iとjを入れ替え、
その後i+1以降の順番を反転させる
と次の数列を求めることができます。
####具体例
具体例を挙げます。
i i+1,j
1 2 3 4 5
ここでは、4<5が最後に現れる昇順の組み合わせです。よってiは4を指します。
また、4より大きい要素は末尾から調べると初めて現れるのは5なので、jは5を指します。
すなわちこの例の場合、i+1=jとなります。
さて、iとjを入れ替えi+1以降を反転(今回はi+1が最後尾なので実質何も起こらない)すると
1 2 3 5 4
となり、辞書順で次の数列を得ます。
もう一つ具体例
i i+1 j
2 1 3 5 4
3<5が最後に現れる昇順のペアで3より大きくて最も後ろにあるのは4です。
iとjを入れ替えるてi+1以降を反転させると
2 1 4 3 5
となり、たしかに辞書順で次の数列です。
####理屈
辞書順で次の数列を作成する時、前の要素だけ変わって後ろの要素が変わらないケースってあり得ないですよね。
そこで変化させる部分について考えると、最後に現れる昇順のペアのインデックスをiとi+1として、次のことが言えます。
辞書順で次であることから、変化させた後の数列について、
- i+1以降は昇順に並んでいないといけない
- iは変化前の数列でi以降にあったもののなかで最も小さい要素かつiより大きい要素
最後に現れる昇順であるというiの選び方より、i+1以降の値は、降順に並んでいることがわかります。
そうでないと、i, i+1が最後の昇順のペアであることに矛盾します。
こんな感じです
i i+1
1 3 5 4 2
| 降順
なので、iより大きい要素はすくなくともi+1があるので、i+1以降には必ず存在し、
その中で最も小さいものは降順なことから後ろから探せば見つかることがわかります。
まとめると、
- i, i+1を見つけ出し、
- iを自分より大きい要素を後ろから探索し入れ替え
- さらにi+1以降を昇順に並び替える
処理を実装すればいいことになります。
というわけで実装しました。
#include <iostream>
#include <algorithm>
bool my_next_permutation(int* array, unsigned int num) {
for (int i = num - 1; i >= 0; i--) {
if (array[i] < array[i+1]) {
int j = num;
do{
j--;
}while (!(array[i] < array[j]));
std::swap(array[i], array[j]);
std::sort(array + i, array+num);
return true;
}
if (i == 0) {
std::reverse(array, array + num);
}
}
return false;
}
int main() {
int array[] = {1, 2, 3, 4};
const unsigned int array_num = 4;
do {
for (int i = 0; i < array_num; i++) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}while (my_next_permutation(array, array_num));
}
結果
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
できました。
ちなみに、sortの部分について
i+1以降は降順です。
そんな中でiの要素より大きい要素の内もっとも後ろのものとiを交換しても、降順は保たれます。
そこで、反転すれば昇順です。
すなわちsortの部分は
std::reverse(array + i+1, array + num);//i+1から末尾までを反転
にできます。
以上のことより、結論が導かれます。
##おわり
あとはこれを++と--だけで記述できればイテレータを用いて汎用的なデータ構造において用いることができます。(std::vector等)
一応実装してみました。
次の順列を作成する計算量は最悪でも要素の数 / 2です
#include <iostream>
#include <algorithm>
template <class BidirectionalIterator>
bool generic_next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
//要素が0または1の場合は終了
if (first == last) return false;
BidirectionalIterator second = first;
++second;
if (second == last) return false;
BidirectionalIterator i = last;
--i; //itを最後尾にセット
while (true) {
BidirectionalIterator prev_i = i;
if (*(--i) < *prev_i) {
BidirectionalIterator j = last;
while (!(*i < *--j));
std::swap(*i, *j);
std::reverse(prev_i, last);
return true;
}
if (i == first) {
std::reverse(first, last);
return false;
}
}
}
int main() {
int array[] = {1, 2, 3, 4};
const int array_num = 4;
do {
for (int i = 0; i < array_num; i++) {
std::cout << array[i] << " ";
}
std::cout << std::endl;
}while (generic_next_permutation(array, array + array_num));
}
++と--が読みづらいだけかと思ったら、理屈も僕にとってはちょっと複雑でした。
自分でもびっくりするくらい読みづらかったので修正しました
もう少し文を修正しました