最初Pythonで10分以上かかっていたので、高速化を考えてみた。
列挙する候補の数には、以下の条件がある。
1. 000001で始まる。
2. 1で終わる。
3. 0と1は同数、すなわち16個ずつある。
1と2でこうなる。
N = 5
M = 2 ** N
L = 2 ** (M - N)
def gen_number():
for n in xrange(L / 2 + 1, L, 2):
yield n
また3の条件で、
def gen_number_core(k, l):
if l == 0:
yield 0
elif l <= k:
for n in gen_number_core(k - 1, l - 1):
yield n + (1 << k - 1)
if l < k:
for n in gen_number_core(k - 1, l):
yield ndef gen_number():
for n in gen_number_core(M - N - 2, M / 2 - 2):
yield L + 1 + (n << 1)
これで約2分になった。
もう少し詳細に見てみる。まず、00000が頭にある。0000はない。あったとすると、00001が2つ見つかることになるから。000はある。10001があるから。00は2つ以上ある。10011と10010があるから。0は3つ以上ある。10101と11011があるから。以上を考え合わせると、連続する0は、
00000 000 00 00 0 0 0 0
となる。1も同様。
よって、最初は00000で、あとは1の連続と0の連続が交互に現れる。あとは組合せ。
def gen_comb(a, k = 0, s = 0, b0 = 0):
m, n = a[k]
if k == len(a) - 1:
b = b0[:]
for l in range(len(b)):
if b[l] == 0:
b[l] = m
yield b
else:
if k == 0:
s = sum(map(lambda e: e[1], a))
b0 = [ 0 ] * s
for e in combinations(range(s), n):
b = b0[:]
i = 0
j = 0
for l in range(len(b)):
if b[l] == 0:
if e[i] == j:
b[l] = m
i += 1
if i == n:
break
j += 1
for c in gen_comb(a, k + 1, s - n, b):
yield cdef gen_number():
for a, b in product(gen_comb([ (3, 1), (2, 2), (1, 4) ]),
gen_comb([ (5, 1), (3, 1), (2, 2), (1, 4) ])):
n = (1 << b[0]) - 1
for k in range(7):
n <<= a[k] + b[k+1]
n += (1 << b[k+1]) - 1
yield n
これで2秒になった。
ただ、これだとN=6につながらなそうなんだよねえ。あとで考える。
