C#でプロジェクトオイラーを解く（問題２４「辞書式順列」）

Tweet

Pocket

どーも、みつおです。

あと１問解いたら、レベル１だ！！！

問題

順列とはモノの順番付きの並びのことである. たとえば, 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万番目はいくつか?

出典：Problem24

解答

using System;

namespace Problem24
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();
        }

        private static string Solve()
        {
            string ret = "";

            int no = 0;
            string tmp = "";
            for (int i0 = 0; i0 < 10; i0++)
            {
                for (int i1 = 0; i1 < 10; i1++)
                {
                    if (i0 == i1) continue;
                    for (int i2 = 0; i2 < 10; i2++)
                    {
                        if (i0 == i2 || i1 == i2) continue;
                        for (int i3 = 0; i3 < 10; i3++)
                        {
                            if (i0 == i3 || i1 == i3 || i2 == i3) continue;
                            for (int i4 = 0; i4 < 10; i4++)
                            {
                                if (i0 == i4 || i1 == i4 || i2 == i4 || i3 == i4) continue;
                                for (int i5 = 0; i5 < 10; i5++)
                                {
                                    if (i0 == i5 || i1 == i5 || i2 == i5 || i3 == i5 || i4 == i5) continue;
                                    for (int i6 = 0; i6 < 10; i6++)
                                    {
                                        if (i0 == i6 || i1 == i6 || i2 == i6 || i3 == i6 || i4 == i6 || i5 == i6) continue;
                                        for (int i7 = 0; i7 < 10; i7++)
                                        {
                                            if (i0 == i7 || i1 == i7 || i2 == i7 || i3 == i7 || i4 == i7 || i5 == i7 || i6 == i7) continue;
                                            for (int i8 = 0; i8 < 10; i8++)
                                            {
                                                if (i0 == i8 || i1 == i8 || i2 == i8 || i3 == i8 || i4 == i8 || i5 == i8 || i6 == i8 || i7 == i8) continue;
                                                for (int i9 = 0; i9 < 10; i9++)
                                                {
                                                    //同じ数値が使われていないか判定
                                                    if (i0 == i9 || i1 == i9 || i2 == i9 || i3 == i9 || i4 == i9 || i5 == i9 || i6 == i9 || i7 == i9 || i8 == i9) continue;
                                                    no++;

                                                    //各桁の数値を連結
                                                    tmp = i0.ToString() + i1.ToString() + i2.ToString() + i3.ToString() + i4.ToString() + i5.ToString() + i6.ToString() + i7.ToString() + i8.ToString() + i9.ToString();
                                                    
                                                    //100万番目の値を取得
                                                    if (no == 1000000)
                                                    {
                                                        ret = tmp;
                                                        break;
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        
            return ret;
        }
    }
}

出力

2783915460