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

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。

問６２　「立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ」
立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる:
56623104 (3843) と 66430125 (4053) である.
41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.
立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.

－－－－－





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





私の解答例は以下です。畳んでいます。

def f(n):
	j = 0
	while True:
		j += 1
		L = [i*i*i for i in xrange(10**j)]
		M = [[str(s).count(str(t)) for t in xrange(10)] for s in L]
		for s in M:
			t = M.count(s)
			if t>=n:
				P = [i for i, u in enumerate(M) if s==u]
				N = [L[i] for i in P]
				return N[0], N, P

n = 5
print f(n)

最初は立方数の１つひとつの順列を作り、それが立方数かチェックしようとしましたが、１分では処理が終わりません。
そこで、立方数の１つひとつを構成する数字別個数リストを作って、同じリストになるものの数が指定個数になるかチェックするようにしました。

関数を１つ使っています。

１．関数f(n)
・j = 0
　変数jは10の累乗ごとに区切ってチェックするのでその累乗値カウンタです。初期クリアします。

・while True:
　無限ループです。

・j += 1
　累乗カウントをカウントアップします。

・L = [i*i*i for i in xrange(10**j)]
　Lは立方数リストです。10**jは10のj乗で、0からこの値までを１区切りにして処理を続けます。

・M = [[str(s).count(str(t)) for t in xrange(10)] for s in L]
　Mは数字別個数リストのリストです。二重の内包表記です。
　まず外側の内包表記の「for s in L」で先ほどの立方数リストLから１つずつ取り出しfor文の前の内側の内包表記に渡します。
　次に内側の内包表記の「for t in xrange(10)」で、ループ変数tに0以上10未満の整数が１つずつ設定されfor文の前に渡されます。
　「str(s).count(str(t))」で、立方数sに含まれる0以上10未満のいずれかのtの個数を数えます。
　例えば、s=1006012008の場合、内側の内包表記は[5,2,1,0,0,0,1,0,1,0]です。
　このような内側の内包表記が数字別個数リストで、外側の内包表記でそれをさらにリストにためています。

・for s in M:
　Mは数字別個数リストのリストから１つずつ取り出した数字別個数リストをループ変数sに設定します。

・t = M.count(s)
　リストMにある、ループ変数sの数字別個数リストと同じものの件数を数えtとします。

・if t>=n:
　上記tが指定個数n以上ならば、問題に合います。

・P = [i for i, u in enumerate(M) if s==u]
　Pは問題にあう立方数の元の数のリストです。
　enumerate関数で0からの連番を発生させます。このインデックス値が立方数の元の数です。

・N = [L[i] for i in P]
　リストPの値をインデックス値に立方数リストLから値を集め、リストNとします。

・return N[0], N, P
　問題に合う最小の立方数、桁を置換した立方数のリスト、その元の数のリストの３つを呼び出し元に返します。
　
２．関数の外
・n = 5
　print f(n)
　問題に合うように指定個数を5個として関数fで関連情報リストも含めて取得し、表示します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。(127035954683L,
[127035954683L, 352045367981L, 373559126408L, 569310543872L, 589323567104L],
[5027, 7061, 7202, 8288, 8384])
（追記）
・20130127　ネタバレ注意の追記など