BohYoh.comトップページへ
C & C++ FAQ
目次

C++ 順列の生成方法を教えてください。

 たとえば、四つの要素があれば、4×3×2通りの方法で順列を生成できます。C++では、辞書順で順列を生成するライブラリが提供されます。<algorithm>のnext_permutationとprev_permutationを利用しましょう。それぞれ、辞書順で一つ次/前の順列を生成します。

using namespace std { template<class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); template<class BidirectionalIterator, class Compare> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); template<class BidirectionalIterator> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last); template<class BidirectionalIterator, class Compare> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp); }

 string型文字列"ABCD"をもとに順列を列挙するプログラム例を示します。
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

/* 順列を生成(string型) */ #include <string> #include <iostream> #include <algorithm> using namespace std; int main(void) { string s = "ABCD"; cout << s << '\n'; while (next_permutation(s.begin(), s.end())) cout << s << '\n'; return (0); }


 C言語スタイルの文字列"ABCD"をもとに順列を列挙するプログラム例を示します。
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

/* 順列を生成(Cスタイル文字列型) */ #include <cstring> #include <iostream> #include <algorithm> using namespace std; int main(void) { char s[] = "ABCD"; cout << s << '\n'; while (next_permutation(s, s + strlen(s))) cout << s << '\n'; return (0); }


 整数の配列1, 2, 3, 4をもとに順列を列挙するプログラム例を示します。
{ 1 2 3 4 }
{ 1 2 4 3 }
{ 1 3 2 4 }
{ 1 3 4 2 }
{ 1 4 2 3 }
{ 1 4 3 2 }
{ 2 1 3 4 }
{ 2 1 4 3 }
{ 2 3 1 4 }
{ 2 3 4 1 }
{ 2 4 1 3 }
{ 2 4 3 1 }
{ 3 1 2 4 }
{ 3 1 4 2 }
{ 3 2 1 4 }
{ 3 2 4 1 }
{ 3 4 1 2 }
{ 3 4 2 1 }
{ 4 1 2 3 }
{ 4 1 3 2 }
{ 4 2 1 3 }
{ 4 2 3 1 }
{ 4 3 1 2 }
{ 4 3 2 1 }

/* 順列を生成(整数の配列) */ #include <iostream> #include <algorithm> using namespace std; void print_intary(int x[], int n) { cout << "{ "; for (int i = 0; i < n; i++) cout << x[i] << " "; cout << "}\n"; } int main(void) { int x[] = {1, 2, 3, 4}; int nx = sizeof(x) / sizeof(x[0]); print_intary(x, nx); while (next_permutation(x, x + nx)) print_intary(x, nx); return (0); }



■ 根拠 ■
標準C++ 25.3.9 Permutation generators

戻る

BohYoh.comロゴ