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);
}

　Ｃ言語スタイルの文字列"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
/*
    順列を生成（Ｃスタイル文字列型）
*/

#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);
}

■ 根拠 ■
標準Ｃ++ 25.3.9 Permutation generators
戻る
BohYoh.comロゴ