日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問題を再掲します。
問９３「算術式」
集合 {1, 2, 3, 4} の各数字をちょうど一度用い, また四則演算 (+, －, *, /) と括弧を使うことにより, 異なる正の整数を作ることができる.
例えば,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) － 1
36 = 3 * 4 * (2 + 1)
12 + 34 のように数字をつなげることは許されないことに注意しよう.
集合 {1, 2, 3, 4} を使うと, 36 を最大とする 31 個の異なる数が得られる.
最初の表現できない数に会うまで, 1 から 28 の各数を得ることができる.
最長の連続した正の整数 1 から n の集合を得ることができる, 4 つの異なる数字 a < b < c < d を見つけよ. 答えを文字列 abcd として与えよ.
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
def f(n):
import itertools
d = {}
for wi in xrange(1, n+1):
for xj in itertools.combinations(xrange(1, 10), wi):
zk = int("".join([str(i) for i in xj]))
d[zk] = []
for vm in range(wi//2):
for pk in itertools.combinations(xj, vm+1):
a = int("".join([str(i) for i in pk]))
b = int("".join([str(i) for i in xj if i not in pk]))
if a>b: continue
for i in d[a]:
for j in d[b]:
d[zk] += [i+j, i-j, j-i, i*j, 1.0*i/j, 1.0*j/i]
if d[zk]: d[zk] = set([s for s in d[zk] if s])
else: d[zk] = [zk]
vol = 0
for i in d.keys():
if i<10**(n-1): continue
j = 1
while j in d[i]: j += 1
if vol<j-1: ans, vol = i, j-1
return ans, vol
n = 4
ans, vol = f(n)
print "ans:",ans
print "vol:",vol
1桁少ない桁数までの計算結果を再利用する方法です。
数式に使用する数字の個数を順に増やしていきます。
総当りよりも速く、4桁以上の桁数でも動作します。
初期設定として、1桁の場合にその数自身だけの配列（リスト）を設定します。
桁数ループwで1桁ずつ増やしつつ、
1から9までの数字から重複無しで桁数分w個だけ数字を選びます。
この数字の組xのすべての並び替えパターンを1つずつ試していきます。
数字の組xの要素で構成された数値zが計算対象です。
この数値を表記上の前半と後半の2つに分けます。
前半の数aが後半の数bよりも大きいとすることで重複計算を防ぎます。
このa,bはzよりも必ず桁数が小さいので、すでに計算済みです。
そしてzの計算として、a,bの計算結果同士を総当りで四則演算します。
計算前に結果をためる配列を、数値zをキーにした連想配列（辞書）dの要素として準備しておきます。
足し算と掛け算は演算子の前後を入れ替えても同じですが、
引き算と割り算は演算子の前後を入れ替えた値も計算し配列にためていきます。
すべてのzについて計算が終わったら最長連続の判定をします。
n桁の数字iをキーにして、計算結果辞書dの要素、つまり数値iの計算結果配列d[i]について、
1から順にいくつまで連続して要素があるかを確認します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
ans: 1258
vol: 51
