「prolog勉強プロジェクトオイラー151～160」の編集履歴（バックアップ）一覧に戻る
プロジェクトオイラーの問題を堀江伸一さんが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
のようになります。
降順という性質を利用して全組み合わせを計算します。
具体例で考えてみましょう。
２６文字から抜き出して12文字作る場合を考えてみます。
昇順になってる２文字が5,10なら
-5の左に11～26までをa文字
-６,7,8,9の何文字かを5の左にｂ文字
-上の残りから何文字かを１０の右にｃ文字
-1～4までの何文字かを１０の右にｄ文字
として12＝a+b+c+dとなりこの組み合わせ数を求めます。
5や10をほかの組に変え全組み合わせを計算して合計すればn＝１２文字の場合の答えが出ます。
ｎがほかの値の場合も同様に求まります。
この発想で実装したコードは以下の通り。
実行するとわかりますが５秒もかかるとても遅いコードです。
次回は私なりに考えた早いC++コードを掲載する予定です。
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).
*問158 C++版
ｃ++コードただいま準備中。
発想は簡単です。
降順になってる２つの数字列があり、大きいほうから考えてこの２つのどちらかに数字を振り分けるかそれともその数字を捨てるかと考えます。
できた数列は以下のようになります。
(9 7 6 2)(8,4,3)
すると重要な情報は、
-左の降順の終わりが右の降順数列のトップより小さい。
-何文字使ったか。
-集計するとき右と左に最低１文字以上割り振ってるか。
この３つ以外考慮する必要がないと分かります。
これを考えるとまず２～26までの数を一文字だけ右に割り振ります。
計算のためのmemo配列を考えてその上で計算します。
memo[a][b][c]
a=0左に割り振られてない
a=1左に割り振られたが右の最大値よりまだでかい
a=2左に割り振られていて左のラストが右のトップより小さい
bは文字の長さ0～２６文字。
cは右側の最大値２～26
でこれをループすれば非常に小さい計算量で問題が解けます。
ｂやｃあたり配列からビット数字列にすればさらに高速になりますがそこまでするとコードがかなり意味不明な暗号になるので手を出しません。
