<p>我将首先提到,在O(n)中有一种演绎方法,它在<a href="https://www.cnblogs.com/lz87/p/11518225.html" rel="nofollow noreferrer">blog post</a>中有详细说明。它可以归结为检查列表中三种类型的元素计数的奇偶性,以确定出现的几个固定结果中的哪一个。在</p>
<p>您提到您更喜欢使用递归方法,即O(n!)。这是一个很好的开始,因为它可以作为帮助实现O(n)解决方案的工具,并且是一种需要熟悉的常见递归模式。在</p>
<p>因为我们不知道两个量子点之间的一个给定的融合是否最终会导致一个最优的全局解,我们不得不尝试所有的可能性。我们通过浏览列表来寻找潜在的融合。当我们找到一个时,在一个新列表中执行转换并对其调用<code>fuse_quxes</code>。在这一过程中,我们会跟踪所达到的最小长度。在</p>
<p>有一种方法:</p>
<pre><code>def fuse_quxes(quxes, choices="RGB"):
fusion = {x[:-1]: [x[-1]] for x in permutations(choices)}
def walk(quxes):
best = len(quxes)
for i in range(1, len(quxes)):
if quxes[i-1] != quxes[i]:
sub = quxes[:i-1] + fusion[quxes[i-1], quxes[i]] + quxes[i+1:]
best = min(walk(sub), best)
return best
return walk(quxes)
</code></pre>
<p>这几乎就是您所提供的代码所朝的方向,但是实现似乎不清楚。不幸的是,我没有看到任何单一或快速的解决办法。以下是一些一般性问题:</p>
<ul>
<li><p>将<code>fusionCreatures1</code>函数放入一个类中,允许它改变外部状态,即<code>self.value</code>和{<cd4>}。<code>self.value</code>尤其是名字不好,很难追踪。其目的似乎是将其用作引用副本,将<code>arr</code>重置为其默认值,但是<code>arr = self.value</code>意味着当<code>fusion()</code>中的<code>fus_arr</code>发生突变时,<code>self.value</code>也是如此。所有的东西几乎都是对一个潜在列表的引用。在</p>
<p>将切片添加到这些副本中至少可以使程序更容易推理,例如,<code>arr = self.value[:]</code>和{<cd12>}函数中的<code>fusion()</code>。简而言之,试着写<a href="https://en.wikipedia.org/wiki/Pure_function" rel="nofollow noreferrer">pure functions</a>。在</p>
<p><code>self.ans</code>也不清楚而且不必要;最好将结果值放在递归函数中的局部变量中。在</p>
<p>似乎没有必要将无状态函数放入类中,除非它是一个纯静态方法,并且该类充当名称空间。</p></li>
<li><p>认知过载的另一个原因是分支语句,如<code>if</code>和{<cd16>}。我们要尽量减少它们的频率和嵌套。以下是伪代码中的<code>fusionCreatures1</code>,带有突变和复杂交互作用的注释:</p>
^{pr2}$
<p>你可能会同意,在精神上逐步完成这个功能是相当困难的。</p></li>
<li><p>在<code>fusionCreatures1()</code>中,有两个变量未使用:</p>
<pre><code> arr1 = self.fusion(arr, i)
testlen = self.fusionCreatures1(arr)
</code></pre>
<p>赋值<code>arr1 = self.fusion(arr, i)</code>(连同<code>return fus_arr</code>)似乎表示缺乏对<code>self.fusion</code>实际上是一个改变其参数数组的<a href="https://en.wikipedia.org/wiki/In-place_algorithm" rel="nofollow noreferrer">in-place</a>函数的理解。所以调用它意味着<code>arr1 is arr</code>,我们还有另一个别名变量需要考虑。在</p>
<p>除此之外,程序中没有使用<code>arr1</code>或{<cd24>},因此其目的不明确。在</p>
<p>一个好的<a href="https://realpython.com/python-code-quality/" rel="nofollow noreferrer">linter</a>将获取这些未使用的变量,并确定我提到的大多数其他复杂问题。</p></li>
<li>对列表进行循环修改通常是灾难性的。<code>self.fusion(arr, i)</code>在循环中变异{<cd6>},这使得很难推断其长度,并且当{<cd27>}不再与函数体中的实际{<cd28>}匹配时(或者至少需要一个in-body先决条件),就很难判断它的长度并导致索引错误。如上所述,使用一个切片使<code>self.fusion(arr, i)</code>为纯,解决了这个问题,但揭示了没有递归的<a href="https://en.wikipedia.org/wiki/Recursion#base_case" rel="nofollow noreferrer">base case</a>,从而导致堆栈溢出错误。在</li>
<li>避免变量名,如<code>arr</code>、<code>arr1</code>、<code>value</code>,除非上下文明显。同样,这些混淆了意图,使程序难以理解。在</li>
</ul>
<p>一些次要的风格建议:</p>
<ul>
<li>根据<a href="https://www.python.org/dev/peps/pep-0008/" rel="nofollow noreferrer">PEP-8</a>使用<code>snake_case</code>。类名应该是<code>TitleCased</code>,以区别于函数。不需要从<code>object</code>继承,这是隐式的。在</li>
<li>在函数和运算符之间使用一致的间距:<code>range (0,len(arr)-1):</code>与{<cd37>}相比更清晰。在块周围使用垂直空格。在</li><li>使用列表而不是键入<code>t1</code>,<code>t2</code>。。。<code>t7</code>。在</li>
<li>函数名应该是动词,而不是名词。像<code>fusionCreatures</code>这样的具有<code>fusionCreatures1</code>方法的类是不清楚的。类似<code>QuxesSolver.minimize(creatures)</code>的东西使意图更加明显。在</li>
</ul>
<hr/>
<p>至于我上面提供的解决方案,还有其他一些技巧值得考虑以加快速度。一个是<a href="https://en.wikipedia.org/wiki/Memoization" rel="nofollow noreferrer">memoization</a>,它可以帮助避免重复的工作(任何给定的列表都将产生相同的最小长度,因此我们只需将此计算存储在dict中,如果我们再次看到它,就把它吐出来)。如果我们的长度达到1,这是我们在全局范围内所能做的最好的,所以我们可以跳过其余的搜索。在</p>
<p>这是一个完整的运行程序,包括翻译成Python的线性解决方案(同样,请参考博客文章了解它的工作原理):</p>
<pre><code>from collections import defaultdict
from itertools import permutations
from random import choice, randint
def fuse_quxes_linear(quxes, choices="RGB"):
counts = defaultdict(int)
for e in quxes:
counts[e] += 1
if not quxes or any(x == len(quxes) for x in counts.values()):
return len(quxes)
elif len(set(counts[x] % 2 for x in choices)) == 1:
return 2
return 1
def fuse_quxes(quxes, choices="RGB"):
fusion = {x[:-1]: [x[-1]] for x in permutations(choices)}
def walk(quxes):
best = len(quxes)
for i in range(1, len(quxes)):
if quxes[i-1] != quxes[i]:
sub = quxes[:i-1] + fusion[quxes[i-1], quxes[i]] + quxes[i+1:]
best = min(walk(sub), best)
return best
return walk(quxes)
if __name__ == "__main__":
tests = [
['R','G','B','G','B'],
['R','G','B','R','G','B'],
['R','R','G','B','G','B'],
['G','R','B','R','G'],
['G','R','B','R','G','R','G'],
['R','R','R','R','R'],
['R', 'R', 'R', 'G', 'G', 'G', 'B', 'B', 'B']
]
for test in tests:
print(test, "=>", fuse_quxes(test))
assert fuse_quxes_linear(test) == fuse_quxes(test)
for i in range(100):
test = [choice("RGB") for x in range(randint(0, 10))]
assert fuse_quxes_linear(test) == fuse_quxes(test)
</code></pre>
<p>输出:</p>
<pre class="lang-none prettyprint-override"><code>['R', 'G', 'B', 'G', 'B'] => 1
['R', 'G', 'B', 'R', 'G', 'B'] => 2
['R', 'R', 'G', 'B', 'G', 'B'] => 2
['G', 'R', 'B', 'R', 'G'] => 1
['G', 'R', 'B', 'R', 'G', 'R', 'G'] => 2
['R', 'R', 'R', 'R', 'R'] => 5
['R', 'R', 'R', 'G', 'G', 'G', 'B', 'B', 'B'] => 2
</code></pre>