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 = n0, n1, … , nm-1, nmの場合で考える。
まず全パターン数Pを求める。
(m+1)×m×…×2×1 = (m+1)!


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


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


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


コード
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;
        }
    }
}
答え

 2783915460



場合の数 2―作業性の特訓 書き上げて解く組み合わせ (思考力算数練習張シリーズ 24)

場合の数 2―作業性の特訓 書き上げて解く組み合わせ (思考力算数練習張シリーズ 24)

組合せ論入門

組合せ論入門

「なぜ? どうして?」をとことん考える高校数学 (BERET SCIENCE)

「なぜ? どうして?」をとことん考える高校数学 (BERET SCIENCE)