<p><strong>解决方案A</strong></p>
<p>我建议将该计划的关注点分为多个功能:</p>
<pre class="lang-py prettyprint-override"><code>def binaries(n):
for m in range(2 ** n):
yield f"{m:>0{n}b}"
</code></pre>
<pre class="lang-py prettyprint-override"><code>print(list(binaries(3)))
</code></pre>
<pre class="lang-py prettyprint-override"><code>['000', '001', '010', '011', '100', '101', '110', '111']
</code></pre>
<p>现在我们可以写<code>pairwise</code>,它在一个iterable上成对迭代-</p>
<pre class="lang-py prettyprint-override"><code>from itertools import tee, islice
def pairwise(t):
a, b = tee(t)
yield from zip(a, islice(b, 1, None))
</code></pre>
<pre class="lang-py prettyprint-override"><code>print(list(pairwise("011001")))
</code></pre>
<pre class="lang-py prettyprint-override"><code>[('0', '1'), ('1', '1'), ('1', '0'), ('0', '0'), ('0', '1')]
</code></pre>
<p>现在很容易将<code>solution</code>实现为所有<code>binaries</code>大小<code>n</code>的组合,其中<code>pairwise</code>对任何特定二进制的分析不包含两个相邻的零-</p>
<pre class="lang-py prettyprint-override"><code>def solution(n):
for b in binaries(n):
for p in pairwise(b):
if p == ('0','0'):
break
else:
yield b
</code></pre>
<pre class="lang-py prettyprint-override"><code>print(list(solution(3)))
</code></pre>
<pre class="lang-py prettyprint-override"><code>['010', '011', '101', '110', '111']
</code></pre>
<p>如果所有人都只需要一个解决方案的计数,我们可以将<code>count_solutions</code>写为<code>solutions</code>-</p>
<pre class="lang-py prettyprint-override"><code>def count_solutions(n):
return len(list(solution(n)))
</code></pre>
<pre class="lang-py prettyprint-override"><code>print(count_solutions(3))
</code></pre>
<pre class="lang-py prettyprint-override"><code>5
</code></pre>
<p>让我们来看一个更大的例子,<code>n</code>=8-</p>
<pre class="lang-py prettyprint-override"><code>print(list(solutions(8)))
print(count_solutions(8))
</code></pre>
<pre class="lang-py prettyprint-override"><code>['01010101', '01010110', '01010111', '01011010', '01011011', '01011101', '01011110', '01011111', '01101010', '01101011', '01101101', '01101110', '01101111', '01110101', '01110110', '01110111', '01111010', '01111011', '01111101', '01111110', '01111111', '10101010', '10101011', '10101101', '10101110', '10101111', '10110101', '10110110', '10110111', '10111010', '10111011', '10111101', '10111110', '10111111', '11010101', '11010110', '11010111', '11011010', '11011011', '11011101', '11011110', '11011111', '11101010', '11101011', '11101101', '11101110', '11101111', '11110101', '11110110', '11110111', '11111010', '11111011', '11111101', '11111110', '11111111']
55
</code></pre>
<hr/>
<p><strong>解决方案B</strong></p>
<p>我一直在思考这个问题,我不喜欢上面的解决方案中的数字在比较之前如何转换成字符串</p>
<p>首先我们写<code>bitwise</code>-</p>
<pre class="lang-py prettyprint-override"><code>def bitwise(n, e):
if e == 0:
return
else:
yield from bitwise(n >> 1, e - 1)
yield n & 1
</code></pre>
<pre class="lang-py prettyprint-override"><code>for n in range(2 ** 3):
print(tuple(bitwise(n, 3)))
</code></pre>
<pre class="lang-none prettyprint-override"><code>(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
</code></pre>
<p>然后<code>pairwise</code>-</p>
<pre class="lang-py prettyprint-override"><code>from itertools import tee, islice
def pairwise(t):
a, b = tee(t)
yield from zip(a, islice(b, 1, None))
</code></pre>
<pre class="lang-py prettyprint-override"><code>for n in range(2 ** 3):
print(bin(n), list(pairwise(bitwise(n, 3))))
</code></pre>
<pre class="lang-py prettyprint-override"><code>0b0 [(0, 0), (0, 0)]
0b1 [(0, 0), (0, 1)]
0b10 [(0, 1), (1, 0)]
0b11 [(0, 1), (1, 1)]
0b100 [(1, 0), (0, 0)]
0b101 [(1, 0), (0, 1)]
0b110 [(1, 1), (1, 0)]
0b111 [(1, 1), (1, 1)]
</code></pre>
<p>最后<code>solution</code>-</p>
<pre class="lang-py prettyprint-override"><code>def solution(e):
for n in range(2 ** e):
for p in pairwise(bitwise(n, e)):
if p == (0, 0):
break
else:
yield n
</code></pre>
<pre class="lang-py prettyprint-override"><code>sln = list(map(bin, solution(3)))
print(sln)
print(len(sln))
</code></pre>
<pre class="lang-py prettyprint-override"><code>['0b10', '0b11', '0b101', '0b110', '0b111']
5
</code></pre>
<p>和<code>n</code>=8-</p>
<pre class="lang-py prettyprint-override"><code>sln = list(map(bin, solution(8)))
print(sln)
print(len(sln))
</code></pre>
<pre class="lang-py prettyprint-override"><code>['0b1010101', '0b1010110', '0b1010111', '0b1011010', '0b1011011', '0b1011101', '0b1011110', '0b1011111', '0b1101010', '0b1101011', '0b1101101', '0b1101110', '0b1101111', '0b1110101', '0b1110110', '0b1110111', '0b1111010', '0b1111011', '0b1111101', '0b1111110', '0b1111111', '0b10101010', '0b10101011', '0b10101101', '0b10101110', '0b10101111', '0b10110101', '0b10110110', '0b10110111', '0b10111010', '0b10111011', '0b10111101', '0b10111110', '0b10111111', '0b11010101', '0b11010110', '0b11010111', '0b11011010', '0b11011011', '0b11011101', '0b11011110', '0b11011111', '0b11101010', '0b11101011', '0b11101101', '0b11101110', '0b11101111', '0b11110101', '0b11110110', '0b11110111', '0b11111010', '0b11111011', '0b11111101', '0b11111110', '0b11111111']
55
</code></pre>
<hr/>
<p><strong>建议阅读</strong></p>
<p>如果您从未在Python中看到过<code>for..else</code>循环,请<a href="https://docs.python.org/3/tutorial/controlflow.html#break-and-continue-statements-and-else-clauses-on-loops" rel="nofollow noreferrer">read the docs</a>了解这个奇妙的构造</p>