Project Euler : Problem 24 『Lexicographic permutations』

列 / aun333

問題

projecteuler.net

　0,1,2,3,4,5,6,7,8,9を重複の無いように組み合わせる。
作れる全ての数字を辞書順に並び替えたとき、100万番目に来る数字は何か？

力技でやるなら

　全パターンを配列に突っ込んで並び替えて100万番目を出力すればいい。
でも確実に100万以上あるのが分かってるしなぁ。

　とりあえず全パターンがいくらあるのか計算してみる。
文字は0から9の10通りだから、
10! = 10×9×8×7×6×5×4×3×2×1 = 3628800
だいたい363万通り。
多すぎるので力技は却下の方向で。

全体から見てどの位置にいるのかを考える

　使える文字がN = n₀, n₁, … , n_m-1, n_mの場合で考える。
まず全パターン数Pを求める。
(m+1)×m×…×2×1 = (m+1)!

　辞書順ランクr+1番目の値を求める場合、(m+1)!を今取れる文字数m+1で割る。
(m+1)!/(m+1) = m!
次に求めたいランク-1の値をm!で割る。
r/m! = p₀ … q₀
m_p₀を得て、Nからm_p₀を消す。

　次はm!を今取れる文字数mで割る。
m!/m = (m-1)!
前回の余りのq₀を(m-1)!で割る。
q₀/(m-1)! = p₁ … q₁
そしてm_p₁を得て、Nからm_p₁を消す。
あとはm=1になるまでくりかえすだけ。

　qを出現順にp₀p₁…p_mと並べると、求めたいランクの文字になっている。

コード

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Problem24
{
    class Program
    {
        static List<int> digits = new List<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

        static void Main(string[] args)
        {
            Int64 allPatternNum = Factorial(digits.Count);


            Debug.WriteLine(RankingNumber(allPatternNum, 1000000));

        }

        /// <summary>
        /// n!を求める
        /// </summary>
        static Int64 Factorial(int n)
        {
            if (n == 0) return 0;

            Int64 p = 1;

            for (int i = 2; i <= n; i++)
            {
                p *= i;
            }

            return p;
        }

        /// <summary>
        /// n番目の番号を求める
        /// </summary>
        /// <param name="apn">全パターン数</param>
        /// <param name="rank">求める値が何番目か</param>
        static String RankingNumber(Int64 apn, Int64 rank)
        {
            //ランクは1番から始まる＆最大数以上はなし
            if (rank <= 0) return "うわっ…私のRank、低すぎ…？";
            if (rank > apn) return "常識的に考えてRank高すぎ";
            rank--;

            List<int> d = new List<int>(digits);
            String s = string.Empty;


            for (int i = d.Count; i >= 1; i--)
            {
                apn = apn / i;
                int p = (int)(rank / apn);
                rank = rank % apn;
                s += d[p].ToString();
                d.RemoveAt(p);
            }

            return s;
        }
    }
}