next_permutationについて調べた

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブックに書いてあった、next_permutationを試してみた。こんなSTLがあったとは知らんかったな。

void permutation_int (int n)
{
    int *perm = new int[n];

    for (int i = 0; i < n; i++) {
        perm[i] = i;
    }

    do {
        for (int i = 0; i < n; i++) {
            std::cout << perm[i] << " ";
        }
        std::cout << "\n";
    } while (std::next_permutation (perm, perm + n));

    return;
}

permに最初に必要な要素を入れておけば、next_permutationを実行する度に異なる組み合わせをpermに生成してくれる。 これはperm[]は再利用されるのか？実際に加工して何かに使いたいならば、一旦コピーを取ったほうが良さそうだね。

./permutation
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1
1 0 2 3
1 0 3 2
1 2 0 3
1 2 3 0
1 3 0 2
1 3 2 0
2 0 1 3
2 0 3 1
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0

これ、vectorとかでも使えるんだろうか。

void permutation_vector(void)
{
    std::vector<std::string> perm;

    perm.push_back ("Hello");
    perm.push_back ("World");
    perm.push_back ("My name is");
    perm.push_back ("Msyksphinz");

    do {
        for (int i = 0; i < 4; i++) {
            std::cout << perm[i] << ",";
        }
        std::cout << "\n";
    } while (std::next_permutation (perm.begin(), perm.end()));

}

コンパイルしてみた。

./permutation
Hello,World,My name is,Msyksphinz,
Msyksphinz,Hello,My name is,World,
Msyksphinz,Hello,World,My name is,
Msyksphinz,My name is,Hello,World,
Msyksphinz,My name is,World,Hello,
Msyksphinz,World,Hello,My name is,
Msyksphinz,World,My name is,Hello,
My name is,Hello,Msyksphinz,World,
My name is,Hello,World,Msyksphinz,
My name is,Msyksphinz,Hello,World,
My name is,Msyksphinz,World,Hello,
My name is,World,Hello,Msyksphinz,
My name is,World,Msyksphinz,Hello,
World,Hello,Msyksphinz,My name is,
World,Hello,My name is,Msyksphinz,
World,Msyksphinz,Hello,My name is,
World,Msyksphinz,My name is,Hello,
World,My name is,Hello,Msyksphinz,
World,My name is,Msyksphinz,Hello,

ちゃんと使えるようね！ただし、pop_backとかして、while中にvectorの中身を変えてしまう(要素を減らしてしまったり)と、正しく処理ができないようだ。 やはり、一旦コピーして使うのが良いのかな。