next_permutation

[機能]

　　系列の各要素を辞書的順序で並べた場合において，現在の並べ方の次になる並べ方を返します．次の並べ方が存在しない場合，辞書的順序における最初の並べ方に並べ替えます．たとえば，a，b，c という 3 つの要素からなる系列の場合，辞書的順序でこれらを並べると，以下のようになります．

　　a b c， a c b， b a c， b c a， c a b， c b a

2 引数の比較関数を指定することも可能です（下の表現，sort 参照）．

[形式]

#include <algorithm>

template <class BidirectionalIterator>
    bool next_permutation(BidirectionalIterator first,
                          BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
    bool next_permutation(BidirectionalIterator first,
                          BidirectionalIterator last, Compare comp);		

[使用例]

1. next_permutation， prev_permutation， is_permutation の使用方法です．以下に示すプログラム例において，いくつかのコメント部分は，その上に記述された方法とほぼ同等なものであることを示しています．

   #include <stdio.h>
   #include <iostream>
   #include <vector>
   #include <algorithm>
   
   using namespace std;
   
   int main()
   {
   					// 初期設定
   	vector<char> v1 {'a', 'b', 'c'};
   	printf("v1 : ");
   	for (auto x : v1)
   		printf("%c", x);
   	printf("\n");
   					// 次の並びを順に出力
   	bool b = true;
   	printf("次の並びを順に出力\n");
   	while (b) {
   		b = next_permutation(v1.begin(), v1.end());
   		if (b) {
   			printf("  ");
   			for (auto x : v1)
   				printf("%c", x);
   		}
   		else {
   			printf("\n");
   			printf("  次の並び順は存在しません\n");
   		}
   	}
   					// 初期設定
   	vector<char> v2 {'b', 'c', 'a'};
   	printf("v2 : ");
   	for (auto x : v2)
   		printf("%c", x);
   	printf("\n");
   					// 前の並びを順に出力
   	b = true;
   	printf("前の並びを順に出力\n");
   	while (b) {
   		b = prev_permutation(v2.begin(), v2.end());
   		if (b) {
   			printf("  ");
   			for (auto x : v2)
   				printf("%c", x);
   		}
   		else {
   			printf("\n");
   			printf("  前の並び順は存在しません\n");
   		}
   	}
   					// 初期設定
   	vector<char> v3 {'b', 'x', 'a'};
   	printf("v3 : ");
   	for (auto x : v3)
   		printf("%c", x);
   	printf("\n");
   					// 順列か？
   	b = is_permutation(v1.begin(), v1.end(), v2.begin());;
   //	b = is_permutation(v1.begin(), v1.end(), v2.begin(), v2.end());;
   	cout << boolalpha << "  v2 は v1 の順列？ : " << b << endl;
   	b = is_permutation(v1.begin(), v1.end(), v3.begin());;
   //	b = is_permutation(v1.begin(), v1.end(), v3.begin(), v2.end());;
   	cout << "  v3 は v1 の順列？ : " << b << endl;
   
   	return 0;
   }
   			

   （出力）

   v1 : abc
   次の並びを順に出力
     acb  bac  bca  cab  cba
     次の並び順は存在しません
   v2 : bca
   前の並びを順に出力
     bac  acb  abc
     前の並び順は存在しません
   v3 : bxa
     v2 は v1 の順列？ : true
     v3 は v1 の順列？ : false
   			

[参照]

sort， prev_permutation， is_permutation