内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用
对于每一个F,S,它计数的内积是零,直到第一个非零内积。代码如下:
#!/usr/bin/python from __future__ import division import itertools import operator import math n=14 m=n+1 def innerproduct(A, B): assert (len(A) == len(B)) s = 0 for k in xrange(0,n): s+=A[k]*B[k] return s leadingzerocounts = [0]*m for S in itertools.product([-1,1], repeat = n): S1 = S + S for F in itertools.product([-1,1], repeat = n): i = 0 while (i<m): ip = innerproduct(F, S1[i:i+n]) if (ip == 0): leadingzerocounts[i] +=1 i+=1 else: break print leadingzerocounts
的正确输出n=14
是
[56229888, 23557248, 9903104, 4160640, 1758240, 755392, 344800, 172320, 101312, 75776, 65696, 61216, 59200, 59200, 59200]
使用PyPy,n=14需要1分18秒。
在我的机器上,C版本代码在100秒内解决了n=20的问题!
import itertools def necklaces_with_multiplicity(n): assert isinstance(n, int) assert n > 0 w = [1] * n i = 1 while True: if n % i == 0: s = sum(w) if s > 0: yield (tuple(w), i * 2) elif s == 0: yield (tuple(w), i) i = n - 1 while w[i] == -1: if i == 0: return i -= 1 w[i] = -1 i += 1 for j in range(n - i): w[i + j] = w[j] def leading_zero_counts(n): assert isinstance(n, int) assert n > 0 assert n % 2 == 0 counts = [0] * n necklaces = list(necklaces_with_multiplicity(n)) for combo in itertools.combinations(range(n - 1), n // 2): for v, multiplicity in necklaces: w = list(v) for j in combo: w[j] *= -1 for i in range(n): counts[i] += multiplicity * 2 product = 0 for j in range(n): product += v[j - (i + 1)] * w[j] if product != 0: break return counts if __name__ == '__main__': print(leading_zero_counts(12))
c版本:
#include <stdio.h> enum { N = 14 }; struct Necklace { unsigned int v; int multiplicity; }; static struct Necklace g_necklace[1 << (N - 1)]; static int g_necklace_count; static void initialize_necklace(void) { g_necklace_count = 0; for (unsigned int v = 0; v < (1U << (N - 1)); v++) { int multiplicity; unsigned int w = v; for (multiplicity = 2; multiplicity < 2 * N; multiplicity += 2) { w = ((w & 1) << (N - 1)) | (w >> 1); unsigned int x = w ^ ((1U << N) - 1); if (w < v || x < v) goto nope; if (w == v || x == v) break; } g_necklace[g_necklace_count].v = v; g_necklace[g_necklace_count].multiplicity = multiplicity; g_necklace_count++; nope: ; } } int main(void) { initialize_necklace(); long long leading_zero_count[N + 1]; for (int i = 0; i < N + 1; i++) leading_zero_count[i] = 0; for (unsigned int v_xor_w = 0; v_xor_w < (1U << (N - 1)); v_xor_w++) { if (__builtin_popcount(v_xor_w) != N / 2) continue; for (int k = 0; k < g_necklace_count; k++) { unsigned int v = g_necklace[k].v; unsigned int w = v ^ v_xor_w; for (int i = 0; i < N + 1; i++) { leading_zero_count[i] += g_necklace[k].multiplicity; w = ((w & 1) << (N - 1)) | (w >> 1); if (__builtin_popcount(v ^ w) != N / 2) break; } } } for (int i = 0; i < N + 1; i++) { printf(" %lld", 2 * leading_zero_count[i]); } putchar('\n'); return 0; }
您可以通过利用符号对称性(4x)和只迭代通过第一个内积测试的向量(渐变,O(sqrt(N))x)来获得一些加速。
import itertools n = 10 m = n + 1 def innerproduct(A, B): s = 0 for k in range(n): s += A[k] * B[k] return s leadingzerocounts = [0] * m for S in itertools.product([-1, 1], repeat=n - 1): S1 = S + (1,) S1S1 = S1 * 2 for C in itertools.combinations(range(n - 1), n // 2): F = list(S1) for i in C: F[i] *= -1 leadingzerocounts[0] += 4 for i in range(1, m): if innerproduct(F, S1S1[i:i + n]): break leadingzerocounts[i] += 4 print(leadingzerocounts)
C版本,为了了解我们对PyPy损失了多少性能(PyPy为16,大致相当于C为18):
#include <stdio.h> enum { HALFN = 9, N = 2 * HALFN }; int main(void) { long long lzc[N + 1]; for (int i = 0; i < N + 1; i++) lzc[i] = 0; unsigned int xor = 1 << (N - 1); while (xor-- > 0) { if (__builtin_popcount(xor) != HALFN) continue; unsigned int s = 1 << (N - 1); while (s-- > 0) { lzc[0]++; unsigned int f = xor ^ s; for (int i = 1; i < N + 1; i++) { f = ((f & 1) << (N - 1)) | (f >> 1); if (__builtin_popcount(f ^ s) != HALFN) break; lzc[i]++; } } } for (int i = 0; i < N + 1; i++) printf(" %lld", 4 * lzc[i]); putchar('\n'); return 0; }