「プロジェクトオイラー問２４」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問２４ - (2014/02/13 (木) 20:37:39) のソース

*問24
Problem 24 「辞書式順列」 †
順列とはモノの順番付きの並びのことである. たとえば, 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万番目はいくつか?


解法
計算しやすいように0123456789　を０番目の数として計算します。
最初の一桁目は
0から始まる数が9！通り
1から始まる数が2*9！通り
2から始まる数が3*9！通り
3だと１００万を超えるので一桁目は２．
残りも同様の方法で決まる。


 fact(0,1):-!.
 fact(N,Result):-N1 is N-1,fact(N1,Re),Result is Re*N.
 
 calc(_,_,[],Ans,Ans):-
 	!.
 calc(No,F,Seed,Ans,Result):-
 	fact(F,NowNo),
 	P is No // NowNo,
 	NextNo is No mod NowNo,
 	nth0(P,Seed,NowE),
 	select(NowE,Seed,Seed1),
 	append(Ans,[NowE],Ans1),
 	F1 is F-1,
 	write([P,No]),nl,
 	calc(NextNo,F1,Seed1,Ans1,Result).
 
 seed(N):-
 	between(0,9,N).
 
 main24:-
 	findall(N,seed(N),Seed),
 	calc(999999,9,Seed,[],Ans),
 	write(Ans).