Project Euler 32(2)

見方を変えて、まず、左辺第2項を固定します。そうすると第1項の範囲が絞れます。例えば、第2項が2だったら、第1項は1000〜4999であることがわかります。そして掛け算をして、数字が1回ずつ使われているかをチェックします。
コードによる速度の違いをチェックしましょう。その前に、計算量を概算します。Nを基数とします。10進ならN=10です。12進なら、N=12で、11個の数字で同様の掛け算を表現します。最初のコードは

(N-1)!*[N/4] ≒ (N-1)N/eN/4 ≒ NN/eN+1/4

個の組合せについてチェックします。3番目のコードは少し難しいですが、

N[(N-1)/2] / 2 + … + N[(N-1)/2] / N[N/4] ≒ N[(N+1)/2]logN[N/4] ≒ N[(N+3)/2]logN/4

となります。本当はもっと小さいです。
上を下で割り算すると、

N[N/2]-1logN/eN+1

と、Nが大きくなれば1より圧倒的に大きくなります。実際に時間を計ってみると(単位:秒)、

N code1 code2 code3
10 6.792 0.843 0.126
11 75.14 11.72 1.198
12 1166. 113.9 4.853
13 - 1944. 53.91
14 - - 183.2

段々差が広がっていくことがわかります。



def gen_digits(n):
while n:
yield n % N
n /= N

def mark(c, n):
for d in gen_digits(n):
if d == 0:
return 0
elif c >> d & 1:
return 0
c |= 1 << d
return c

def gen_pandigits():
for k in range(1, M / 2 + 1):
start = 2 if k == 1 else N ** (k - 1)
for m in xrange(start, N ** k):
c1 = mark(0, m)
if c1 == 0: # duplicated?
continue
min_n = max(N ** (M - k - 1), (N ** (N - M - 2) + m - 1) / m)
max_n = min(N ** (M - k), (N ** (N - M - 1) + m - 1) / m)
for n in xrange(min_n, max_n):
c2 = mark(c1, n)
if c2 == 0:
continue
c2 = mark(c2, n * m)
if c2 != 0:
yield n * m

N = 14 # base
M = N / 2 # number of left digits
s = set(gen_pandigits())
print sum(s)