プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ。 Problem 158 「左隣の文字より辞書順で後になる文字がちょうど1個となる文字列を探し当てよ」 † http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20158 26文字のアルファベットから3個の異なった文字を取ると, 長さ3の文字列を作ることができる. 例えば, 'abc', 'hat', 'zyx'となる. この3つの例について調べると, 'abc'は左隣の文字より辞書順で後になる文字が2個ある. 'hat'では, 左隣の文字より辞書順で後になる文字がちょうど1個となり, 'zyx'では0個となる. 左隣の文字より辞書順で後になる文字がちょうど1個となるような長さ3の文字列は全部で10400個存在する. いま, n ≤ 26 個の異なった文字について考える. nについて, p(n) を左隣の文字より辞書順で後になる文字がちょうど1個となるような長さnの文字列の個数であるとする. p(n) の最大値を求めよ. 解法。 うまい解法を思いつきませんでした。 a=1,b=2,,,z=26として数字に置き換えます。 たとえば左寄り辞書順で後ろの文字のセットが一か所 5,10 とあったとします。 右は5より小さい数が必ず配置可能でその0～何個かの並びは必ず降順です。 左は１０より大きな数は必ず配置可能でその0～何個かの並びは昇順です。 そして間の6,7,8,9は右か左に配置します。 右ならどんな選び方をしても抜き取ったものは降順に並べるしかありませんし、左に配置するなら抜き取ったものは昇順に並べるしかありません。 14,13,12,9,8(5,10)7,6,4,2,1 のようになります。 あとはこの場合での全組み合わせを計算します。 答えは５.184秒で出ますがまだ遅い感じがします。 たぶん数式を突き詰めればとても小さな計算量で解けるはずですが私にはちょっと手が届きそうもありません。 sum([],0):-!. sum([X|Xs],Result):-!,sum(Xs,Re),Result is Re+X. combin(_,0,A,B,Result):-!,Result is A//B. combin(N,M,A,B,Result):- !, N1 is N-1, M1 is M-1, A1 is A*N, B1 is B*M, combin(N1,M1,A1,B1,Result). combin(N,M,Result):-combin(N,M,1,1,Result). calc(N,Result):- between(2,26,R), T is R-1, between(1,T,L), CenterSize is R-L-1, RightSize is 26-R, LeftSize is L-1, between(0,CenterSize,CExtraction), CExtraction=<N, between(0,CExtraction,CExtractionL), between(0,CExtraction,CExtractionR), CExtractionR is CExtraction-CExtractionL, CSizeL is CenterSize, CSizeR is CenterSize-CExtractionL, between(0,LeftSize,LExtraction), LExtraction+CExtraction+2=<N, RExtraction is N-CExtraction-LExtraction-2, 0=<RExtraction, RExtraction=<RightSize, combin(CSizeL,CExtractionL,CPL), combin(CSizeR,CExtractionR,CPR), combin(LeftSize ,LExtraction,LP), combin(RightSize ,RExtraction,RP), Result is CPL*CPR*LP*RP. test1(Sum):- between(2,26,N), findall(Perm,calc(N,Perm),Perms), sum(Perms,Sum). print_ans([]):-!. print_ans([Perm|Perms]):-write(Perm),nl,print_ans(Perms). main158:- findall(Sum,test1(Sum),Sums), print_ans(Sums).
