C++
アルゴリズム
競技プログラミング

next_permutationがイマイチよくわからなかったのでまとめてみた


概要

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以上

  • 要素は整数(<演算子が使えればなんでもいいですが簡単のため)

  • 予めソート済み
    ということで考えていきます。


辞書順で次の数列をどうやってつくるのか

結論から言えば

先頭から探索し最後に現れるi, i+1のペアにおいて、

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

できました。

しかし実はまだ工夫できます。

i+1以降は降順です。

そんな中でiの要素より大きい要素の内もっとも後ろのものとiを交換しても、降順は保たれます。

そこで、反転すれば昇順です。

すなわち、先程のコードのsort部分を

            std::reverse(array + i+1, array + num);//i+1から末尾までを反転

に変更すればおkです。

以上のことより、結論が導かれます。


おわり

あとはこれを++と--だけで記述できればイテレータを用いて汎用的なデータ構造において用いることができます。(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));
}

++と--が読みづらいだけかと思ったら、理屈も僕にとってはちょっと複雑でした。

自分でもびっくりするくらい読みづらかったので修正しました

説明がうまくなりたいです。

また誤解している部分などあれば指摘頂けるとありがたいです。