欧拉计划第265题：二进制圈

$2^N$个二进制位可以排成一圈，使得所有按顺时针顺序得到的N位二进制子串都不一样。

对于N=3，不考虑旋转，有两种可行的排圈方式：

在第一种排圈方式中，按顺时针顺序得到的3位二进制子串分别是：000、001、010、101、011、111、110和100。

每一种排圈方式都可以按如下方式编码：以全为0的子串作为起点，将所有的二进制位连接起来。N=3的两种排圈方式于是就可以编码为23和29：
$(00010111{)}_2=23$
$(00011101{)}_2=29$

记S(N)是所有排圈方式的编码之和，我们可以看到S(3) = 23 + 29 = 52。

求S(5)。

---

解：

遍历所有情况，需要遍历 2**32 = 4294967296种情况，我使用了带剪枝的回溯算法。1秒多完成计算。

这里用了一个评估函数，不同子串的个数，如果出现了相同的子串，则返回-1，用于剪枝。

def next_seq(seq, max_len, prune=False):
    if not prune and len(seq) < max_len:
        seq.append('0')
        return seq
    d = seq.pop()
    while d == '1':
        d = seq.pop()
    seq.append('1')
    return seq


def eval(state, k):
    strings = set()
    for i in range(0, len(state)):
        substring = ''.join(state[i:i+k])
        while len(substring) < k and len(state) == 2**k:
            substring += '0'
        if len(substring) == k:
            if substring in strings:
                return -1  # 这个返回值，用于回溯时的剪枝
            strings.add(substring)
    return len(strings)


# print(eval(list('00010111'), 3))
# print(eval(list('0001011'), 3))
# print(eval(list('00000111110111001101011000100101'), 5))


def euler265(N):
    result = []
    state = ['0'] * N
    while state:
        if any(c == '1' for c in state[:N]):  # 前5个必须为'0', 遍历到 00001...时，就结束了
            break
        e = eval(state, k=N)
        if e < 0:
            # print('BACK', ''.join(state))
            state = next_seq(state, max_len=2**N, prune=True)  # 剪枝
        else:
            if e == 2**N:
                num = int(''.join(state), base=2)
                result.append(num)
                # break # 如果仅要一个答案，就break
            state = next_seq(state, max_len=2**N)
    return sum(result)


assert euler265(3) == 52
print(euler265(5))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51