全列挙神降臨

C#からC++に乗り換えたからいままでの記事は一体何だったのか
そもそも前の更新がいつか覚えてないあばばばばばｂ

どうでもいいけど全列挙神関数　next_permutation　 が降臨したから
これはチラシの裏に書きなぐらなければならない

http://www.cplusplus.com/reference/algorithm/next_permutation/

何をする関数かというと（前提条件→）昇順にソートされた配列内のn要素の順列を順に書き出す関数

僕の勉強し始めて数日のC++力では、
next_permutation(始点のアドレス,終点のアドレス,比較用関数)
があるのは知ってるけど、
next_permutation(始点のアドレス,終点のアドレス)
しか使えないです＞＜；

あと、下のコードではこの怪しいマクロをつかってます。

#define rep(i,val) for(int i = 0; i < val; i++)

何がすごいのか
１． 重複組み合わせが効率的に計算される
O(n!)だからNP困難（？？？）無理ゲー！！　で終わらせる前に、本当はうまく列挙を工夫すれば大幅に計算量をバッサリ切れる。

定式化すると、n要素を愚直に全列挙しようとするとn!だけど、もし、重複分がa1,a2,a3,...個あると、
n!/a1!/a2!/a3!/...と場合の数が減る。
なので、うまく重複分を削れることができれば、数え上げ回数がかなーーーり削減されることになる。
うまく、場合の数を絞り上げればメモ化が捗りそう

下は一次元配列の場合のシンプルな使い方

int main()
{
    int count = 0;
    int syoken[5] = {1,2,3,4,5};
    int syoken_sagi[5] = {1,1,2,2,2};

    do
    {
        count++;
        rep(i,5)
        {
           // cout << syoken[i] << " " << endl;
        }
     //   cout << endl;
    }while (std::next_permutation(syoken, syoken + 5));
    cout << count << endl;
    count = 0;
    do
    { 
        count++;
        rep(i,5)
        {
           // cout << syoken_sagi[i] << " " << endl;
        }
      //  cout << endl;
    }while (std::next_permutation(syoken_sagi, syoken_sagi + 5));
    cout << count << endl;
    return 0;
}

出力結果
120
10

重複分を無駄に計算してたら110回も余分なことをすることになってたのでこれはデカイ

下のコードは二次元配列 {{0,0,0},{3,3,3},{9,9,9}}の全列挙を試したコードで、
countがループの回数を計測してるので、出力結果が9!/3!/3!/3! = 1680 回のループで考えうるすべての場合の数え上げができてる！
重複分を無視して愚直に数え上げしようとすると、9! = 362880回のループになるので、これは　圧　倒　的　削　減
なんかよくわかんないけど array[0]で先頭のアドレス渡すとうまくいけた
なんでだろう、わからない・・・

int main()
{
    int count = 0;
    int syoken[3][3];
    rep(i,3)
        rep(j,3)
        syoken[i][j] = 3*i;
    do
    {
        rep(i,3)
        {
            rep(j,3)
            {
               //cout << syoken[i][j] << " ";
            }
            //cout << endl;
        }
        count++;
        //cout << endl;
    }while (std::next_permutation(syoken[0], syoken[0] + 9));
        cout << count << endl;
    return 0;
}

上のように２次元配列でもアドレスをうまく指定すれば、うまくやってくれるらしい
まぁ、減らせると言ってもn = 50とかになっちゃうと普通に無理
それでも全列挙の心強い味方なのは確定的に明らかで、配列のデータをエンコーディングしてキーとしてもれば、mapとかDictionaryとかでのメモ化が捗りそう（まだやってないけど）

2.実装がくっそ楽
これを自前で実装しようと思ったら繰り返しや再帰の高度なコーディングがいるけど、
do whileとか3行のテンプレでいけちゃう、知ってるか知ってないかで別ゲー

この記事の結論
ぶっちゃけこの記事はただの自分用のメモ、二次元配列の全列挙ができることを書きたかった
どーでもいいけど、do while ってゴミだと思ってたけど（リーダブルコードで読みにくいってdisられてた）ちゃんと有用なのね