問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番目の数として計算します。
最初の一桁目は
0から始まる数が9!通り
1から始まる数が2*9!通り
2から始まる数が3*9!通り
3だと100万を超えるので一桁目は2.
残りも同様の方法で決まる。
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).
最終更新:2014年02月13日 20:37