プロジェクトオイラー 問１０３

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

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

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

ある n に対し S(A) が最小化されていれば, それを最適特殊和集合と呼ぼう. はじめの 5 つの最適特殊和集合は下に与えられる.

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

ある最適集合 A = {a1, a2, ... , an} に対し, 次の最適集合は B = {b, a1+b, a2+b, ... ,an+b} となりそうである. ここで b は前列の「中央の」要素である.

この「法則」を用いると n = 6 に対する最適集合は A = {11, 17, 20, 22, 23, 24} で, S(A) = 117 と予期するだろう. しかしこれは, 最適に近い集合を与えるアルゴリズムを用いたにすぎないため, 最適集合とはならない. n = 6 に対する最適集合は A = {11, 18, 19, 20, 22, 25} で, S(A) = 115 である. これに対応する集合の文字列は 111819202225 である.

A を n = 7 に対する最適特殊集合とするとき, その集合の文字列を求めよ.

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






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def chk1(L):
	import itertools
	M = []
	for i in xrange(len(L)):
		for j in itertools.combinations(L, i+1):
			s = sum(j)
			if s in M: return False
			M.append(s)
	return True

def chk2(L):
	a, b = (len(L)+1)//2, len(L)//2+1
	return sum(L[:a])>sum(L[b:])

def g(L):
	if not L: return [1]
	c = L[(len(L)-1)//2]
	for b in xrange(c, c+L[-1]):
		M = [a+b for a in [0]+L]
		if chk1(M) and chk2(M): return M

def f(n):
	M = []
	for i in xrange(n):
		M, N, k = g(M), [[]], i//2
		for j in M:
			L = xrange(max(1, j-k), j+k+1)
			N = [s+[t] for s in N for t in L if (not s) or s[-1]<t]
		for L in N:
			if sum(L)<sum(M) and chk1(L) and chk2(L): M = L
	return "".join([str(s) for s in M]), sum(M)

n = 7
t, s = f(n)
print "str:", t
print "sum:", s

ゼロベースで最適特殊集合を作り出そうとするととても１分で処理が終わりません。
「最適に近い集合」が提示されているので、まずこれを基に各要素ごとにいくらかの幅を設定して候補値を選定します。
そしてこの「各要素ごとの候補値の組合せ」から最適特殊解集合を求めることにしました。

１．関数chk1(L)
・リストLが最適特殊和集合の以下の条件、
　i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.
　を満たしていればTrue、満たしていなければFalseを返します。
・リストLの部分集合の和を作成し、リストMに無ければためていき、あればFlseで終了します。
・ループ変数iは、リストLから部分集合を作る際に取り出す要素数（0～）です。
・ループ変数jは、組み合わせ関数combinationsを利用して、
　リストLからi+1個の要素を取り出した組み合わせ結果のタプルが設定されます。

２．関数chk2(L)
・リストLが最適特殊和集合の以下の条件、
　ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.
　を満たしていればTrue、満たしていなければFalseを返します。
・この条件を満たすかどうかが一番厳しい部分集合の和同士でチェックします。
・一番厳しい部分集合の和同士は、要素を昇順に並べた集合の中で、
　要素が奇数個の場合、最小値から中央値までの和とそれより後の和同士、
　つまり{1,2,3,4,5}ならば、{1,2,3}と{4,5}の和を比較（この場合False）します。
　要素が偶数個の場合、集合の前半の和と後半の２番目に小さい値以降の和同士、
　つまり{1,2,3,4,5,6}ならば、{1,2,3}と{5,6}の和を比較（この場合False）します。
　
３．関数g(L)
・リストLの次の「最適に近い集合」のリストを返します。
・次の「最適に近い集合」は、問題にあるロジックの通り、中央値と中央値を全要素に足した集合です。
・Lが空集合の場合、要素が1だけのリストを返却します。

４．関数f(n)
・要素数がn個の最適特殊集合の要素連結文字列と和を返します。
・既知の最適特殊集合に基づいて要素数が1つ多い最適特殊集合をもとめていきます。
　要素数が1個から始めてn個になるまで順に最適特殊集合を求めていきます。

・リストMは既知の最適特殊集合で、関数gにより次の「最適に近い集合」を設定します。
・ループ変数iはリストMの要素数です。

・ループ変数jは最適に近い値を１つずつ設定します。
・変数kは候補値の幅です。ここでは「最適に近い集合」の要素数の半分とします。
　要素数が４や５ならば各要素の±２に含まれる値を各要素の候補値とします。
　jのループ中で、各要素ごとの候補値リストLとして持ちます。
・リストNは各要素の候補値の組合せリストです。なお昇順になる組合せのみ採用します。

・候補値組合せリストNのループ内で、リストNの中から最適特殊集合を求めます。
・「最適に近い集合」Mよりも和が小さいこと、最適特殊集合の条件２つに合うかチェックし、最適特殊集合として採用します。
　チェックして合うものが無ければ、「最適に近い集合」Mを最適特殊集合とします。



解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
str: 20313839404245
sum: 255