2015年2月1日日曜日

プロジェクトオイラー 問106

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

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

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

本問題に対しては, 与えられた集合は n 個の単調増加する要素を含み, かつ第二のルールをすでに満たしているものと仮定しよう.

驚くべきことに, n = 4 の集合から得ることができる 25 個の可能な部分集合の対のうち, 
1 個の対のみが 同一性(第一のルール)をテストされる必要がある. 
同様に, n = 7 のときは, 966 個の部分集合の対のうち 70 個のみがテストされる必要がある.

n = 12 に対して, 得られる 261625 個の部分集合の対のうち, 同一性をテストされる必要があるものは何個か.

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





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






私の回答例は以下の通りです。
def f(n):
	import itertools
	c = 0
	for i in xrange(2, n//2+1):
		L = [t for t in itertools.combinations(xrange(n), i)]
		for j, t0 in enumerate(L):
			for t1 in L[:j]:
				for s in t1:
					if s in t0: break
				else:
					for s,t in zip(t0, t1):
						if s<t: c += 1; break
	return c

n = 12
print f(n)





問題文にあるとおり、問103の関連問題です。
まず、与えられた集合はn個の単調増加する要素を含むことが前提なので、要素が2つ以上の部分集合が対象です。
また、ルールiiを満たしていることが前提なので、要素数が同じ部分集合同士が対象外です。
以上から、ルールiをチェックする部分集合ペアとして、以下の条件のものの件数を数えます。
・要素数が同じ
・同じ要素を持たない
・同じ項番の値でその大小が混在すること

なお、総当りで試しているので1分ルールに合うのはn=14までです。
当問題はn=12なのでこの方法でよしとします。

1.関数f(n)
・問題にある、同一性をテストされる必要がある部分集合の個数を返します。
 引数nは特殊和集合の要素数です。
・変数cは求める部分集合数です。
・ループ変数iは、比較する部分集合の要素数です。
 要素数が2個からnの半分までです。半分を超えると必ず同じ要素が含まれてしまいます。
・リストLは、0からn-1までのn個の値からi個選ぶ組合せのタプル群です。
・t0,t1が比較する部分集合の候補同士です。どちらもリストLの要素です。
 重複の無駄を避けるため、enumerate関数で0からの連番を発行し、リストL内の組合せ順でt0よりも先に作成される部分集合からt1として取り出します。

・同じ要素がないことの確認方法は以下の通りです。
 部分集合t1から要素を変数sとして順に取り出し、
変数sが1つでも部分集合t0に存在すれば、ループを終了し次のペアの処理へ進みます。
変数sのすべてで部分集合t0に存在しなければ、else句へ進み次のチェックをします。

・同じ項番の値で大小が混在することの確認方法は以下の通りです。
 zip関数でt0とt1の同じ位置の値をそれぞれs, tとして設定します。
 このときt1の方がt0よりも、組合せ順で先に作成されるので、部分集合t0の要素sよりも部分集合t1の要素tの方が小さい値を持つはずで、これと逆にs<tとなるtが1つでもあれば大小混在となり、チェック対象の部分集合数のカウンタcを1つアップして比較操作を抜けます。
 すべてのs,tで大小混在が検出できなければ、次の比較ペアへ処理を進めます。



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

0 件のコメント:

コメントを投稿