Problem24 順列の100万番目の値

問題

順列とはモノの順番付きの並びのことである.
たとえば, 3124は数1,2,3,4の一つの順列である.
すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ.
0と1と2の順列を辞書順に並べると
012,021,102,120,201,210になる.

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ

ソース

#include <string>
#include <vector>
#include <stack>
#include <iostream>

void main()
{
    std::vector<std::string> JyunretuVect;
    std::stack<std::string> stk;
    std::string strArr[] = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };
    const int strArrUB = sizeof(strArr)/sizeof(strArr[0])-1;

    for (int I = strArrUB; 0 <= I; I--) {
        stk.push(strArr[I]);
    }

    while (stk.empty() == false){
        std::string Popped = stk.top(); stk.pop();

        if(Popped.size() == strArrUB+1){
            JyunretuVect.push_back(Popped);
            if (JyunretuVect.size() == 1000000) break;
            continue;
        }

        for (int I = strArrUB; 0 <= I; I--) {
            if(Popped.find(strArr[I]) == std::string::npos)
                stk.push(Popped + strArr[I]);
        }
    }

    std::cout << JyunretuVect.at(1000000 - 1) << std::endl;
}

実行結果

2783915460

解説

深さ優先探索で、順列の並びの逆順でStackにPushして
順列の数が100万になったら枝切りしてます。