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万番目を答えよ

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var JyunretuList = new List<string>();
        string[] StrArr = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" };

        var Stk = new Stack<string>();
        Stk.Push("2");

        while (Stk.Count > 0) {
            string Popped = Stk.Pop();

            if (Popped.Length == StrArr.Length) {
                JyunretuList.Add(Popped);
                continue;
            }

            for (int I = 0; I <= StrArr.Length - 1; I++) {
                if (Popped.Contains(StrArr[I]) == false)
                    Stk.Push(Popped + StrArr[I]);
            }
        }
        JyunretuList.Sort();
        Console.WriteLine(JyunretuList[274240 - 1]);
    }
}

実行結果

2783915460

解説

9の階乗は362880ですので
1文字目を0として順列は362880通りあり、
1文字目を1として順列も362880通りあります。

362880*2= 725760
362880*3=1088640
1000000-725760=274240
ですので、

1文字目を2とした順列を辞書式にソートし、274240番目が解となります。