学習日記 #1 ~next_permutation~

#0. Hello, Qiita!!
始めまして。とある情報系の大学に通っている大学生です。最近、競技プログラミングを始めて、「自分はまだまだ力不足だ。」と痛感しました。

そこで、競技プログラミングで学んだことを学習日記として記録しよう思います。
今回は記念すべき１回目の投稿です。
Qiita初心者でもあるので、暖かい目で見て行ってください、、。

基本的にc++を使用します。
今回はnext_permutationについて書こうと思います。

#1. はじめに
next_permutationとは簡単に言うと順列生成してくれるものです。
順列生成とは、ある複数の要素の並び順のパターンを全て生成してくれることです。
例えば、{1,2,3}の数列があるとして、その順列の全てのパターンは、

{1,2,3} {1,3,2}
{2,1,3} {2,3,1}
{3,1,2} {3,2,1}

と言うふうな感じです。
このような全ての順列のパターンを出してくれるのが、next_permutationです。

#2. next_permutationを使う
では実際にnext_permutationを利用した簡単なコードを見ていましょう。

:sample.cpp

#include<iostream>
#include<algorithm>

using namespace std;

int main(){
    int a[] = {1,2,3};

    do{
        for(int i = 0; i < 3; i++){
            cout << a[i] << ",";
        }
        cout << endl;
    }while(next_permutation(a, a+3));
    return 0;
}

上から順に見ていきます。
next_permutationを利用するには、algorithmをインクルードしなければなりません。
また、並び替えたい数列は昇順に並んでいないと全てのパターンを
出力することができ無くなります。
do while文を利用して、doの中は全ての順列のパターンを全列挙するようにしました。
また、whileの条件の中にnext_permutationを記述し、引数は数列の範囲を入れます。
next_permutationは、最後から最初の順列を生成した場合のみ false を返し、それ以外の場合は true を返します。

これを実行してみると、

1,2,3,
1,3,2,
2,1,3,
2,3,1,
3,1,2,
3,2,1,

このように、全ての順列のパターンを標準出力してくれます。
next_permutitaionは配列だけでなくコンテナクラス(vectorなど)を使用することもできます。

計算量は、高々(last - first)/2回の要素の交換です。

#3. 最後に
これで新しい知識が増えました！！
最後まで読んでいただきありがとうございます。

また、初めてQiitaを書いたので分かりずらかった点や間違っている点、改善点、など
あると思います。よければコメントでご指摘お願いたします！