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

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

問１１２「はずみ数」
左から右までどの桁もその左の桁を下回らない数を増加数と呼ぶ. 例えば, 134468.
同様に, どの桁もその右の桁を下回らない数を減少数と呼ぶ. 例えば, 66420.
増加数でも減少数でもない正の整数をはずみ数と呼ぶことにする. 例えば, 155349.

100以下にはずみ数が無いのは明らかだが, 1000未満では半数を少し上回る525個がはずみ数である.
実際, はずみ数の割合が50%に達する最少の数は538である.
驚くべきことに, はずみ数はますます一般的になり, 21780でははずみ数の割合は90%に達する.
はずみ数の割合がちょうど99%になる最小の数を求めよ.






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






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

def f(n):
	i, b, c, r = 0, 0.0, 0.0, n/100.0
	while True:
		i += 1
		s = str(i)
		t = "".join([j for j in sorted(s)])
		u = "".join([j for j in sorted(s, reverse=True)])
		if t<s<u: b += 1
		else: c += 1
		if r<=b/(b+c): break

	return i

n=99
s = f(n)
print s

小さい数から順に各桁を昇順降順にソートした値と比較することではずみ数か判定し、件数カウントしその割合を計算しました。

１．関数f(n)
・はずみ数の割合がちょうどn％になる最小の数を返します。
・変数iは候補値、変数bははずみ数の個数、変数cははずみ数以外の個数、変数rは割合です。
・変数sで候補値を文字列にします。
  ループ変数jでひと桁ずつ取り出し、sorted関数で昇順にして再度連結した値を変数tとし、sorted関数のreverse引数をTrueにすることで降順にして再度連結した値を変数uとします。
・変数tとuはそれぞれ増加数と減少数なので、変数sがこれらの間の値であれば、はずみ数と判定します。





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

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

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

問１１１「重複桁を持つ素数」
重複した桁を含む 4 桁の素数を考える. 

全てが同じにならないのは明らかである: 
1111 は 11 で割り切れ, 2222 は 22 で割り切れ, 以下同様だからである. 

しかし 3 個の 1 を含む 4 桁の素数は 9 つある:
1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

n 桁の素数に対する重複した桁の最大個数を M(n, d) と表すことにしよう. 
ここで d は重複した桁とする. 
またそのような素数の個数を N(n, d) と表し, これらの素数の和を S(n, d) と表す.
よって M(4, 1) = 3 は, 重複した桁を 1 としたときの, 
4 桁の素数に対する重複した桁の最大個数である. 
そのような素数は N(4, 1) = 9 個あり, これらの素数の和は S(4, 1) = 22275 である. 
d = 0 に対しては, 重複した桁は M(4, 0) = 2 個だけ可能であることが分かるが,そのような場合は N(4, 0) = 13 個ある.

同じようにして 4 桁の素数に対して次の結果を得る.

Digit, d	M(4, d)	N(4, d)	S(4, d)
0	2	13	67061
1	3	9	22275
2	3	1	2221
3	3	12	46214
4	3	2	8888
5	3	1	5557
6	3	1	6661
7	3	9	57863
8	3	1	8887
9	3	7	48073

d = 0 から 9 に対して, S(4, d) の総和は 273700 である.

S(10, d) の総和を求めよ.






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






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

def h(n):
	import itertools
	if n==2: return True
	if n<2 or (not n%2): return 0
	for i in itertools.islice(itertools.count(3, 2), None):
		if i*i>n: break
		if not n%i: return 0
	return n

def g(M, w):
	L = []
	for s in M:
		if s[0]=="0":
			for t in w:
				L.append(t+s)
		else:
			for i in xrange(len(s)+1):
				for t in w:
					if i==0 and t=="0": continue
					L.append(s[:i]+t+s[i:])
				
	return L

def f(n):
	SS = 0
	for d in xrange(10):
		w = [str(i) for i in xrange(10) if i!=d]
		S, M = 0, n
		while S==0:
			M -= 1
			L = [str(d)*M]
			for i in xrange(n-M): L = g(L, w)
			L = set(L)
			for t in L: S += h(int("".join(t)))
			
		SS += S
		
	return SS

n=10
s = f(n)
print s

素数を発生させて重複桁があるかチェックする方式でやってみたところ、チェック以前に10桁分の素数の発生がとても1分で終わらないことが判明しました。
そこで、やり方を逆にして、まず重複桁の値を決め、その他の値を重複桁の間や両側に付加して候補値を作り、素数チェックをするようにしました。


１．関数h(n)
・素数ならｎ、素数以外なら0を返します。
・問５８の 素数判定関数を改良しました。

・forループではxrange関数で数値を発生させていましたが、
  10桁の整数の途中からオーバーフローになるので
  itertoolsモジュールのislice関数を使うように改良しました。
  
２．関数g(M, w)
・リストMの全要素の両端や文字間に、リストwから取り出した１文字を付加した値を作りリストにまとめて返します。
  但し、後で数値化したときに桁数が減ってしまうことを避けるために、
  リストMの各要素の先頭が0の場合は左端にだけ付加し、
  付加する文字が0の場合は左端以外にだけ付加します。
  

３．関数f(n)
・n桁の素数について問題文のSの合計を返します。
・ループ変数dは重複する桁の値で、0から9の値をとります。
・リストwは重複しない桁の値で、0から9のうち、dと異なる値を持ちます。
・変数Sは、dが重複するn桁の素数の和です。
・変数Mは、重複する桁dの個数です。
・while文では変数Mを１つずつ減らしながらSを計算し0以外になれば終了します。
・変数iは、全体n桁のうちd以外の値の個数です。
・リストLは、関数gでd以外の値をi個付加した候補値のリストです。
  リストLの要素を１つずつ取り出し、連結して数値化し、関数hで素数判定します。
  素数ならば、変数Sに累積していきます。
・whileループを抜けたら、SをSSに累積して、次のdでの処理に続きます。






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

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

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

問１１０「ディオファントス逆数 その2」
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である.

解の数が 4,000,000 を超える最小の n を求めよ.

注: この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.






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






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

def P(n):
	L, i = [], 1
	if n>0:
		L.append(2)
		while len(L)<n:
			i += 2
			for j in L:
				if not i%j: break
			else:
				L.append(i)
	return L

def mul(L): return reduce(lambda x,y:x*y, L)

def f(m):
	import math
	tmax = int(math.log(m*2, 3))
	p = P(tmax+1)
	nb, kb, Lb, L = 0, 0, [], []
	while len(L)<=tmax:
		L = [1]*(len(L)+1)
		M = [i*2+1 for i in L]
		k = (mul(M)+1)//2
		while k<=m:
			for i in xrange(len(L)):
				if tmax<=1 or (i<len(L)-1 and L[i]==L[i+1]):
					L[i] += 1
					for j in xrange(i):
						if L[j]>L[i]: L[j] = L[i]
					break
			else:
				L = [1]*(len(L)+1)

			M = [i*2+1 for i in L]
			k = (mul(M)+1)//2

		N = [p[i]**j for i,j in enumerate(L)]
		n = mul(N)
		if nb==0 or n<=nb: nb, kb, Lb = n, k, L
	return nb, kb, Lb

m=4000000
n, k, L = f(m)
print "n :", n
print "k :", k
print "L :", L

問１０８ではnを１つずつ増やしながら解の個数kを求めてkが閾値を超えたら終了というロジックで解きましたが、解の個数kが巨大な数になると、素因数分解の処理が重くて処理が終わりません。

まず、問１０８からわかっていることは以下のとおりです。
・解の個数kは、n²を２つの約数の積で表したパターンの個数に等しい。

・n²の約数の個数iについて、n²を素因数分解した結果に含まれる各素因数に対して、採用0個の場合も含めたパターン数は各要素数+1であり、これを全素因数の分だけ掛け合わせた積が、約数の個数iということになります。
　例：72の約数の個数は、72=2³＋3², べき乗の値から、(3+1)x(2+1)=12

・n²の約数の個数iとして、２つの約数の積でn²になる組合せの個数kとして、
　k = (i+1)//2  （小数以下切捨て）です。

上記からnと解の個数kの関係を、例にあるn=1260, k=113の場合を手で計算してみると以下の通りです。

n = 1260
↑積　　↓因数分解 
素数とべきリスト値の累乗リストN = [2², 3², 5¹, 7¹] = [4, 9, 5, 7]
↑小さい順の素数にべきリストLの値で累乗
べきリストL = [2, 2, 1, 1]
↓各要素の２乗
べき２乗リスト = [4, 4, 2, 2]
↓各要素に+1する
約数の個数リストM = [5, 5, 3, 3]
↓各要素の積
約数の個数 = 5*5*3*3 = 225
↓
解の個数k = (225+1)//2 = 113

問108ではnから出発して１つずつ因数分解をしていましたが、
一見して明らかに一番取り扱い易そうなのは、上記のべきリストLです。
べきリストLを調整しつつ、kを算出してしきい値判定して、nを特定する方法でいきます。

しきい値mとして、m<kである最小のnを求めるので、
m<kを満たすkが特定されたときにnが最小であるためには、
べきリストLは、左の要素≧右の要素 ...(a)

べきリストLの要素数をtに固定すると、
nが最小になるのは、全要素が1のとき。例　[1,1, ... ,1]　1がt個ある。
べきリストLの要素数tの最大値tmaxは、全要素が1でm=kのときのtの値です。
このとき約数の個数リストMは1*2+1=3だけがtmax個ある状態で、
解の個数k = (3^tmax)//2 = m（しきい値）となります。
3^tmax = m*2
両辺の対数をとって、
tmax * log3 =log(m*2)
tmax = log(m*2)/log3 = log₃(m*2) （小数以下切捨て）...(b)

１．関数P(n)
・小さい方からn個の素数リストを返します。
・Problem108で作成した関数を流用します。詳しくはProblem108を参照。

２．関数mul(L)
・リストLの全要素の積を返します。
・reduce文で、第１引数の関数f、第２引数にリストLを設定しています。
・関数fは「lambda x,y:x*y」です。
　無名関数lambdaを使って、引数１と引数２の積を計算します。
・reduce文では関数fの第２引数にリストLの要素を順に渡し、
　関数fの第１引数に関数処理結果を設定します。
　このため、関数fでfの第１引数と第２引数を元に計算することで、累積的な処理が記述できます。
　reduce文は、累積的は処理を短く記述できますが、少しややこしい構文です。

３．関数f(m)
・1/x + 1/y = 1/n（x,y,nは正の整数）となる解の個数kが引数mを超える最小値を求め、n、k、べきリストLを返します。
・べきリストLの要素数の最大値tmaxは、上記(b)をそのまま実装します。
・素数リストpは、関数Pでtmax個の素数を準備します。

・外側のwhileループでは、べきリストの要素数がtmax以下の場合にべきリストを調整して解の候補を探します。
・べきリストLの初期値は全要素1で要素数をループの都度１つずつ増やします。

・内側のwhileループでは、解の個数kがそのしきい値m以下の場合にべきリストを調整して解の候補を探します。

・現在のべきリストに基づいて次のべきリストを調整します。
・iのforループで、べきリストの要素を右から順に見ていきます。
　まず、べきリストの最大要素数が1以下、または「右隣と同じ値」である最初の要素を+1します。
　例：[1] → [2]
　例：[4, 3, 2, 2, 1, 1] → [4, 3, 3, 2, 1, 1]
　さらに、+1した要素の左側は、L[i]にクリアします。
　例：[4, 3, 3, 2, 1, 1] → [3, 3, 3, 2, 1, 1]
　-1する前のリストは当ループが進めばまた出てきます。
　
・forループが最後まで終了したら、べきリストLの要素数を１つ増やして全要素1にクリアします。
　for文のelse句は、for文のループがbreakで途中で抜けずに最後まで終了した直後に実行する処理を記述します。
　例：[3, 2, 1] → [1, 1, 1, 1]

・このようにしてべきリストLを作成したら、チェックします。
　約数の個数リストM、解の個数kを計算します。

・解の個数kがしきい値を超えて内側のwhileループが終了したら、素数とべきリスト値の累乗リストN、そして求める値nを計算し、バックアップしてある値と比較して、最小のnの場合にバックアップするようにします。




解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
n : 9350130049860600
k : 4018613
L : [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1]

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

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

問１０９「ダーツ」
ダーツゲームでは, プレイヤーは 20 等分に分けられたダーツボードに 3 本のダーツを投げる. 
ダーツボードは 1 から 20 の番号がふられている.

ダーツの点数は, ダーツが刺さった領域の番号によって決まる. 
外側の赤緑の輪の外に刺さったダーツは 0 点である. 
この輪の内側の黒と白の領域はシングル (1 倍) の点数を表している. 
しかし, 外側と内側の赤緑の輪はそれぞれダブル (2 倍) とトリプル (3 倍) の点数である.

ボードの中央の 2 つの同心円はブルやブルズアイと呼ばれる. 
外側のブルは 25 点, 内側のブルはダブルの 50 点である.

ルールには多くのバリエーションがあるが, 最もポピュラーなゲームでは, 
プレイヤーは 301 または 501 点から始まり, 最も早く現在の得点を 0 点に減らしたプレイヤーが勝者となる. 
しかし, 普通は「ダブルアウト」方式でプレイをする. 
この方式では, プレイヤーは勝利するために, 
最後のダーツをダブル (ボードの中央のダブルのブルズアイを含む) に刺さなければならない. 
それ以外で現在の得点を 1 点以下に減らした場合, 
3 本のダーツに対する得点は「バースト(無効)」になる.

プレイヤーが現在の得点で終了できる場合を「チェックアウト」と呼ぶ. 
最も高いチェックアウトは 170: T20 T20 D25 (トリプルの 20 を 2 回とダブルのブル) である.

得点が 6 でチェックアウトする異なるやり方はちょうど 11 通りある.

D3   
D1 D2  
S2 D2  
D2 D1  
S4 D1  
S1 S1 D2 
S1 T1 D1 
S1 S3 D1 
D1 D1 D1 
D1 S2 D1 
S2 S2 D1 

D1 D2 と D2 D1 は, 異なるダブルで終了しているので異なるとみなすことに注意しよう. 
しかし S1 T1 D1 の組み合わせは T1 S1 D1 と同じとみなす.

さらに, 組み合わせを考える上でミスは含まないこととする; 
たとえば, D3 は 0 D3 や 0 0 D3 と同じである.

信じられないことに, 異なるチェックアウトは全部で 42336 通りある.
得点が 100 未満の異なるチェックアウトは何通りあるか.






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






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

def f(n):
	Ls = [i+1 for i in xrange(20)]+[25]
	Ld = [(i+1)*2 for i in xrange(20)]+[50]
	Lt = [(i+1)*3 for i in xrange(20)]
	La = Ls+Ld+Lt
	c = 0

	for i in Ld:
		if i<n: c += 1

	for i in La:
		for j in Ld:
			if i+j<n: c += 1

	for m, i in enumerate(La):
		for j in La[m:]:
			for k in Ld:
				if i+j+k<n: c += 1

	return c

n=100
c = f(n)
print c

何投目で終了するかの別に分けてカウントします。

１．関数f(n)
・n点未満でチェックアウトするときの、場合の数を返します。
・リストLsはシングルの得点リストです。要素は1から20までの整数と25です。
・リストLdはダブルの得点リストです。要素は1から20までの偶数と50です。
・リストLtはトリプルの得点リストです。要素は1から20までの3の倍数です。
・リストLaは全面の得点リストです。
　シングル、ダブル、トリプルのリストを単純に結合したものです。

・１投終了の場合、ダブルのリストLdです。
　この中から得点合計がn未満の場合をカウントします。

・２投終了の場合、１投目は前面リストLa、２投目はダブルのリストLdです。
　二重ループで状況を再現し、得点合計がn未満の場合をカウントします。

・３投終了の場合、
　１投目は前面リストLa、
　２投目は前面リストLaのうち１投目としてカウントしてないもの、
　つまり、リストLaから１投目で採用した位置よりも後の位置で採用します。
　３投目はダブルのリストLdです。
　三重ループで状況を再現し、得点合計がn未満の場合をカウントします。


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

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

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

問１０８「ディオファントス逆数 その1」
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 4 では 3 つの異なる解がある.
1/5 + 1/20 = 1/4
1/6 + 1/12 = 1/4
1/8 + 1/8 = 1/4

解の数が 1000 を超える最小の n を求めよ.

注: この問題は Problem 110 の易しいケースである. こちらを先に解く事を強く勧める.





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






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

def P(n):
	L, i = [], 1
	if n>0:
		L.append(2)
		while len(L)<n:
			i += 2
			for j in L:
				if not i%j: break
			else:
				L.append(i)
	return L

def g(n, P):
	s, d = n, {}
	for i in P:
		while s>=i:
			if s%i: break
			else:
				while not s%i:
					d[i], s = d.get(i, 0)+1, s//i
		if s<i: break
	return d 

def f(m):
	import math
	i = int(math.log(2*m-1, 2))
	n, k, p = 1, 1, P(i)
	while k<=m:
		n += 1
		d = g(n*n, p)
		i = 1
		for j in d.values(): i *= j+1
		k = (i+1)//2
	return n, k

m=1000
n, k = f(m)
print "n :", n
print "k :", k

問題の式を変形してみます。
1/x + 1/y = 1/n
両辺にnxyを掛けて
ny  + nx  = xy
xy - nx - ny = 0 ...a

式aを２つの数の積で表して差分調整することにします。
xy, nx, nyを展開式の項として持つ式で最も簡単な式は以下の通り。
(x-n)(y-n) = xy - nx - ny + n² ...b

式bに式aを代入して、
(x-n)(y-n) = n² ...c

n²を２つの正の整数の積で表し、それぞれ+nすればxとyになります。
つまり、当問題でチェックすべき「解の数」は、
n²を２つの約数の積で表したパターンの個数です。

また、２つの約数の積が元の数になる組合せは、
約数を順に並べて小さい方からと大きい方からそれぞれ１つずつ採用し、
中央値がある場合は中央値を２つ採用した組合せです。
なので、n²の約数の個数i、該当する約数の組合せの個数kとして、以下の通りです。
k = (i+1)/2  （小数点以下切捨て）...d

また、約数の個数iは素因数分解した素因数ごとの採用パターン数の積です。
n²を素因数分解した結果の素因数ごとの要素数jとして、
その採用0個の場合も含めたパターン数j+1について、
全ての素因数の分の積を計算します。
この約数の個数iから、約数ペアの個数kを求め、指定値mを超えるまで処理を繰り返します。

また、素因数分解にあたり素数をいくつまで用意したらいいか検討します。
素因数分解で使用する素数の個数の上限値tについて、
この分だけ最小素数2を累乗しても約数の個数i以上となるので、
2^t ≧ i
両辺の対数を取って、
tlog2 ≧ log(i)
t ≧ log(i)/log2 = log₂i
式dを代入して、
t ≧ log₂(2k-1)
t = log₂(2k-1) （小数点以下切り捨て）...e

素因数分解の準備として、素因数分解で使用する素数の個数の上限値tの分だけ素数を用意しておきます。

１．関数P(n)
・小さい方からn個の素数リストを返します。
・リストLは素数リスト、変数iは素数候補です。
・リストLに最初の素数2を設定します。
・3以上の奇数を素数候補として、リストLにある素数で順に割り算します。
　割り算の余りが無い時点で素数候補iは素数ではないので、
　forループをbreakして次の素数候補へ処理がすすみ、
　リストLのすべての素数で割り算の余りがあれば、forループが最後まで回るのでelse句へ進んで素数リストLに素数候補iを追加します。
・上記を指定した素数の個数になるまで続けます。

２．関数g(n, P)
・Problem47で作成した関数を流用します。詳しくはProblem47を参照。
・引数nを素数リストPを使って素因数分解し、
　素数をキー、キーごとの分解した個数を値とする辞書（連想配列）を返します。

３．関数f(m)
・1/x + 1/y = 1/n（x,y,nは正の整数）となる解の個数kがmを超える最小値を求め、nとkを返します。
・対数関数を使う準備としてmathモジュールをインポートし式eを実装します。
　math.log関数の引数は、真数、底の順に設定します。
　変数nは問題文の右辺1/nのn、変数kはチェック対象の解の個数です。
・whileループで、解の個数kが指定値mを超えるまで処理を繰り返します。
・変数dは関数gによるn²に対して素数リストpを使用して因数分解した結果の辞書（連想配列）です。
・ループ関数jで因数分解辞書dから、素因数の値に関係なく、素因数ごとの要素数を設定します。
　変数iに、該当する素因数の個数j個に0個採用のケースも含めたj+1を掛けてためます。
・変数kとして、式dを実装します。//関数は割り算の商（整数値）です。





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

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

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

問１０７「最短ネットワーク」
以下の無向ネットワークは7つの頂点と重み付きの12個の辺からなり, 重みの総和は243である.

このネットワークを以下の行列で表現することができる.

	A	B	C	D	E	F	G
A	-	16	12	21	-	-	-
B	16	-	-	17	20	-	-
C	12	-	-	28	-	31	-
D	21	17	28	-	18	19	23
E	-	20	-	18	-	-	11
F	-	-	31	19	-	-	27
G	-	-	-	23	11	27	-

しかし, このネットワークを, 全ての頂点が連結であるように適当な辺を除いた上で最適化することが出来る. 節約される量が最大化されるように取り除いたネットワークが以下の画像である. この場合, 辺の重みの総和は93であり, 元のネットワークからの節約量は 243 - 93 = 150 である.

6Kバイトのテキストファイル network.txt (右クリックして保存すること) には40頂点のネットワークを行列表示したものが記されている. ネットワーク全体が連結であるが冗長な辺を取り除いたときの節約量を最大にするようにした場合の節約量を答えよ.





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






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

def f(sIn):
	pIn = open(sIn)
	L0 = pIn.read().replace("\n", ",").split(",")
	pIn.close()
	pIn = None
	n = int(len(L0)**.5)
	L1, a = [], 0
	for i, w in enumerate(L0):
		if not w.isdigit(): continue
		w, (y, x) = int(w), divmod(i, n)
		if x<y:
			L1.append((w, (x, y)))
			a += w

	c, V, E = 0, [i for i in xrange(n)], []
	for w, (v1, v2) in sorted(L1):
		if V[v1]!=V[v2]:
			c += w
			E.append(((v1, v2),w))
			minv, maxv = min(V[v1], V[v2]), max(V[v1], V[v2])
			for i,s in enumerate(V):
				if s==maxv: V[i] = minv
			if not sum(V): break
	return a-c, a, c, E

s = "p107_network.csv"
sIn = os.path.join(os.path.dirname(__file__), s)
s, a, c, E = f(sIn)
print "saving:", s
print "all :", a
print "cut :", c
print "edge:", E

　問題文では「冗長な辺を取り除いて」とありますが、重い辺を順に除外していくと、重い辺の代わりに軽い辺を複数除外する方が全体として軽くなる場合に、重い辺の除外を解除しなくてはいけなくなり、ロジックが複雑になります。
そこで、軽い辺を順に採用していくことにします。
ただし、辺を１つ採用するごとに新しくつながる頂点または頂点群が増えることが条件です。
これを全頂点を網羅するまで続けます。

　頂点または頂点群が増えるかどうかの判定は、各頂点ごとにつながっている最小頂点番号で判定します。
最初は自分だけなので、各頂点とも最小頂点番号に自分自身の頂点番号を設定します。
　そして、重みの軽い辺から順にその両端点の最小頂点番号が異なる場合に採用し、両端点の最小頂点番号も洗い直しておきます。
すべての頂点の最小頂点番号が0になれば終了です。
最大頂点番号でも同様のことが可能ですが、終了判定がわかりやすいので最小頂点番号を使用します。

また、辺には向きが無いので、頂点番号の小さい方から大きい方への辺のみ使用します。

１．関数f(sIn)
ネットワーク情報のcsvファイルを入力し、
重みの節約数、重みの合計、カット後の重み合計、採用する辺のリストを返します。

・L0は:入力ファイルのcsv区切りのリストです。
　改行文字と半角カンマで区切ってリストにします。
・変数nは頂点数です。
　リストL0は各頂点を行列表示しているので、頂点数nはリストL0の平方根になります。
・リストL1は辺のリストです。
　(重み、（頂点番号１、頂点番号２）)のタプルをためます。
　ただし、重みは数値で、頂点番号１＜頂点番号２の場合に限ります。
・aは重みの総合計です。
・wは重み、xは列番号、yは行番号です。
　リストL0は行列表示を一次配列にしているので、
　その通し番号iを頂点数nで割った商が行番号y、余りが列番号xになります。
　divmod関数で商と余りを一度に求めています。

・リストVは最小頂点番号のリストです。
　V[i]は頂点iがつながっている最小頂点番号です。
　初期値は各頂点の自分自身の頂点番号です。
・リストEは採用した辺のリストです。
・辺のリストL1をソートして１つずつ処理します。
　ソートキーは未指定の場合は最初の要素なので、この場合、重みに軽い順になります。
・v1、v2は辺の両端の頂点番号です。
　このそれぞれのつながっている最小頂点番号が異なる場合、
　まだつながっていない頂点または頂点群なので、辺を採用します。
・minv, maxvは、採用した辺の両端点がそれぞれつながっている最小頂点番号の
　小さい方と大きい方です。
　最小頂点番号リストVで、値がこの小さい方の場合、大きい方の値に洗いなおします。
・最後に、最小頂点番号リストVの全要素の和をチェックし、この和が0ならば全頂点から0番目の頂点につながったということになるので処理終了です。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
saving: 259679
all : 261832
cut : 2153
edge: [((21, 36), 1), ((27, 34), 6), ((10, 33), 7), ((28, 34), 9), ((13, 39), 17), ((4, 35), 19), ((9, 29), 25), ((5, 25), 27), ((20, 28), 27), ((3, 9), 32), ((5, 34), 33), ((7, 9), 35), ((8, 15), 36), ((9, 13), 36), ((29, 37), 36), ((11, 17), 41), ((6, 10), 42), ((2, 9), 47), ((28, 37), 48), ((9, 10), 50), ((8, 24), 53), ((10, 19), 53), ((5, 36), 54), ((0, 31), 56), ((5, 23), 66), ((12, 29), 68), ((15, 31), 68), ((16, 18), 73), ((3, 38), 76), ((20, 30), 80), ((22, 28), 83),((14, 26), 89), ((35, 36), 91), ((1, 37), 102), ((26, 32), 102), ((11, 21), 104), ((2, 26), 108), ((1, 16), 122), ((0, 18), 131)]

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

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

問１０６「特殊和集合:メタ検査」
大きさ 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)

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

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

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

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

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



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