「プロジェクトオイラー問１０５」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問１０５」(2014/03/05 (水) 20:29:06) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20105

*Problem 105 「特殊和集合:検査」 †
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.

i. S(B)≠S(C); つまり, 部分集合の和が等しくてはならない.
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

たとえば, {81, 88, 75, 42, 87, 84, 86, 65} は, 65 + 87 + 88 = 75 + 81 + 84 であるため特殊和集合ではないが, {157, 150, 164, 119, 79, 159, 161, 139, 158} はすべての可能な部分集合の対の組み合わせについて両方のルールを満たしており, また S(A) = 1286 である.

7 から 12 の要素を含む 100 個の集合が記された 4K のテキストファイル sets.txt (右クリックして "名前をつけてリンク先を保存") を用いて (上の二例はファイルの最初の 2 集合である), 特殊和集合 A1, A2, ... , Ak をすべて特定し, S(A1) + S(A2) + ... + S(Ak) を求めよ.

注意: この問題は Problem 103 と 106 に関連している.

ファイルや問題の詳細は情報はリンク先参照のこと。



解法
全部の場合を検討しても計算量は大したことになりません。
なので全部の場合で条件を満たしているならと行きたいところですが。
ここで導出木の性質が立ちふさがります。
成功したら次へ進むという性質でこれが少し厄介です。
条件を満たしているなら失敗し、全部の有効な場合で失敗したならそれは正しい集合である。
という解釈で実装します。



 sum([],0):-!.
 sum([X|Xs],Result):-
 	!,
 	sum(Xs,Re),
 	Result is Re+X.
 
 
 check1(0,0,_,_):-!,fail.
 check1(Sum1,Sum1,_,_):-!.
 check1(_,_,Len1,Len1):-!,fail.
 check1(_,_,Len1,Len2):-Len1>Len2,!,fail.
 check1(Sum1,Sum2,_,_):-Sum1<Sum2,!,fail.
 check1(_,_,_,_):-!.
 
 
 check([],List1,List2):-
 	!,
 	length(List1,Len1),
 	length(List2,Len2),
 	sum(List1,Sum1),
 	sum(List2,Sum2),
 	check1(Sum1,Sum2,Len1,Len2).
 
 check([_|Xs],List1,List2):-
 	check(Xs,List1,List2).
 check([X|Xs],List1,List2):-
 	check(Xs,[X|List1],List2).
 check([X|Xs],List1,List2):-
 	check(Xs,List1,[X|List2]).
 
 oklist1(Row):-
 	check(Row,[],[]).
 
 oklist(Rows,Result):-
 	member(Row,Rows),
 	not(oklist1(Row)),
 	sum(Row,Result).
 
 main105:-
  	open('pe105.txt',read,IS),
 	read_term(IS,Rows,[]),
 	close(IS),
 	findall(Sum,oklist(Rows,Sum),Sums),
 	sum(Sums,Ans),
 	write(Ans).

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20105

*Problem 105 「特殊和集合:検査」 †
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.

i. S(B)≠S(C); つまり, 部分集合の和が等しくてはならない.
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

たとえば, {81, 88, 75, 42, 87, 84, 86, 65} は, 65 + 87 + 88 = 75 + 81 + 84 であるため特殊和集合ではないが, {157, 150, 164, 119, 79, 159, 161, 139, 158} はすべての可能な部分集合の対の組み合わせについて両方のルールを満たしており, また S(A) = 1286 である.

7 から 12 の要素を含む 100 個の集合が記された 4K のテキストファイル sets.txt (右クリックして "名前をつけてリンク先を保存") を用いて (上の二例はファイルの最初の 2 集合である), 特殊和集合 A1, A2, ... , Ak をすべて特定し, S(A1) + S(A2) + ... + S(Ak) を求めよ.

注意: この問題は Problem 103 と 106 に関連している.

ファイルや問題の詳細は情報はリンク先参照のこと。



解法
全部の場合を検討しても計算量は大したことになりません。
なので全部の場合で条件を満たしているならと行きたいところですが。
ここでＰｒｏｌｏｇ言語の導出木の性質が立ちふさがります。
成功したら次へ進むという性質でこれが少し厄介です。
条件を満たしているなら失敗し、全部の有効な場合で失敗したならそれは正しい集合である。
という解釈で実装します。



 sum([],0):-!.
 sum([X|Xs],Result):-
 	!,
 	sum(Xs,Re),
 	Result is Re+X.
 
 
 check1(0,0,_,_):-!,fail.
 check1(Sum1,Sum1,_,_):-!.
 check1(_,_,Len1,Len1):-!,fail.
 check1(_,_,Len1,Len2):-Len1>Len2,!,fail.
 check1(Sum1,Sum2,_,_):-Sum1<Sum2,!,fail.
 check1(_,_,_,_):-!.
 
 
 check([],List1,List2):-
 	!,
 	length(List1,Len1),
 	length(List2,Len2),
 	sum(List1,Sum1),
 	sum(List2,Sum2),
 	check1(Sum1,Sum2,Len1,Len2).
 
 check([_|Xs],List1,List2):-
 	check(Xs,List1,List2).
 check([X|Xs],List1,List2):-
 	check(Xs,[X|List1],List2).
 check([X|Xs],List1,List2):-
 	check(Xs,List1,[X|List2]).
 
 oklist1(Row):-
 	check(Row,[],[]).
 
 oklist(Rows,Result):-
 	member(Row,Rows),
 	not(oklist1(Row)),
 	sum(Row,Result).
 
 main105:-
  	open('pe105.txt',read,IS),
 	read_term(IS,Rows,[]),
 	close(IS),
 	findall(Sum,oklist(Rows,Sum),Sums),
 	sum(Sums,Ans),
 	write(Ans).