Python中的递归对日常编码的挑战

Question

我正在尝试解决我在网上发现的一些编码难题。但是我被下面的问题阻止了。我试图用递归来解决它，但我觉得我缺少了递归中一个非常重要的概念。我的代码适用于以下所有示例，但最后一个示例将崩溃。在

有人能指出我在这个递归代码中犯的错误吗？或者引导我解决这个问题？在

我知道我的代码为什么会中断，但我不知道如何避开Python中的“pass-by-object-reference”，我认为这会给我带来更大的问题。在

编码问题是：

On a mysterious island there are creatures known as Quxes which come in three colors: red, green, and blue. One power of the Qux is that if two of them are standing next to each other, they can transform into a single creature of the third color.

Given N Quxes standing in a line, determine the smallest number of them remaining after any possible sequence of such transformations. For example, given the input ['R', 'G', 'B', 'G', 'B'], it is possible to end up with a single Qux through the following steps:

        Arrangement       |   Change
----------------------------------------
['R', 'G', 'B', 'G', 'B'] | (R, G) -> B
['B', 'B', 'G', 'B']      | (B, G) -> R
['B', 'R', 'B']           | (R, B) -> G
['B', 'G']                | (B, G) -> R
['R']                     |
________________________________________

我的代码是：

class fusionCreatures(object):
    """Regular Numbers Gen.
    """

    def __init__(self , value=[]):
        self.value = value
        self.ans = len(self.value)


    def fusion(self, fus_arr, i):
        color = ['R','G','B']
        color.remove(fus_arr[i])
        color.remove(fus_arr[i+1])
        fus_arr.pop(i)
        fus_arr.pop(i)
        fus_arr.insert(i, color[0])
        return fus_arr


    def fusionCreatures1(self, arr=None):
        # this method is to find the smallest number of creature in a row after fusion 
        if arr == None:
            arr = self.value
        for i in range (0,len(arr)-1):
            #print(arr)
            if len(arr) == 2 and i >= 1 or len(arr)<2:
                break
            if arr[i] != arr[i+ 1]:
                arr1 = self.fusion(arr, i)
                testlen = self.fusionCreatures1(arr)
                if len(arr) < self.ans:
                    self.ans = len(arr)
        return self.ans

测试阵列（除最后一个外，所有阵列都工作）：

^{pr2}$

Answer 1

这是我的建议。在

首先，我使用整数值0、1和2来代替“R”、“G”和“B”。这使得a和{}之间的融合非常简单，只要它们不同，只需做3 - a - b。在

那么我的递归代码是：

def fuse_quxes(l):
    n = len(l)
    for i in range(n - 1):
        if l[i] == l[i + 1]:
            continue
        else:
            newn = fuse_quxes(l[:i] + [3 - l[i] - l[i + 1]] + l[i+2:])
            if newn < n:
                n = newn
    return n

运行这个

^{pr2}$

Answer 2

我将首先提到，在O（n）中有一种演绎方法，它在blog post中有详细说明。它可以归结为检查列表中三种类型的元素计数的奇偶性，以确定出现的几个固定结果中的哪一个。在

您提到您更喜欢使用递归方法，即O（n！）。这是一个很好的开始，因为它可以作为帮助实现O（n）解决方案的工具，并且是一种需要熟悉的常见递归模式。在

因为我们不知道两个量子点之间的一个给定的融合是否最终会导致一个最优的全局解，我们不得不尝试所有的可能性。我们通过浏览列表来寻找潜在的融合。当我们找到一个时，在一个新列表中执行转换并对其调用fuse_quxes。在这一过程中，我们会跟踪所达到的最小长度。在

有一种方法：

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)

这几乎就是您所提供的代码所朝的方向，但是实现似乎不清楚。不幸的是，我没有看到任何单一或快速的解决办法。以下是一些一般性问题：

• 将fusionCreatures1函数放入一个类中，允许它改变外部状态，即self.value和{}。self.value尤其是名字不好，很难追踪。其目的似乎是将其用作引用副本，将arr重置为其默认值，但是arr = self.value意味着当fusion()中的fus_arr发生突变时，self.value也是如此。所有的东西几乎都是对一个潜在列表的引用。在

  将切片添加到这些副本中至少可以使程序更容易推理，例如，arr = self.value[:]和{}函数中的fusion()。简而言之，试着写pure functions。在

  self.ans也不清楚而且不必要；最好将结果值放在递归函数中的局部变量中。在

  似乎没有必要将无状态函数放入类中，除非它是一个纯静态方法，并且该类充当名称空间。

• 认知过载的另一个原因是分支语句，如if和{}。我们要尽量减少它们的频率和嵌套。以下是伪代码中的fusionCreatures1，带有突变和复杂交互作用的注释：

  ^{pr2}$

  你可能会同意，在精神上逐步完成这个功能是相当困难的。

• 在fusionCreatures1()中，有两个变量未使用：

          arr1 = self.fusion(arr, i)
          testlen = self.fusionCreatures1(arr)
  

  赋值arr1 = self.fusion(arr, i)（连同return fus_arr）似乎表示缺乏对self.fusion实际上是一个改变其参数数组的in-place函数的理解。所以调用它意味着arr1 is arr，我们还有另一个别名变量需要考虑。在

  除此之外，程序中没有使用arr1或{}，因此其目的不明确。在

  一个好的linter将获取这些未使用的变量，并确定我提到的大多数其他复杂问题。

• 对列表进行循环修改通常是灾难性的。self.fusion(arr, i)在循环中变异{}，这使得很难推断其长度，并且当{}不再与函数体中的实际{}匹配时（或者至少需要一个in-body先决条件），就很难判断它的长度并导致索引错误。如上所述，使用一个切片使self.fusion(arr, i)为纯，解决了这个问题，但揭示了没有递归的base case，从而导致堆栈溢出错误。在
• 避免变量名，如arr、arr1、value，除非上下文明显。同样，这些混淆了意图，使程序难以理解。在

一些次要的风格建议：

• 根据PEP-8使用snake_case。类名应该是TitleCased，以区别于函数。不需要从object继承，这是隐式的。在
• 在函数和运算符之间使用一致的间距：range (0,len(arr)-1):与{}相比更清晰。在块周围使用垂直空格。在
• 使用列表而不是键入t1，t2。。。t7。在
• 函数名应该是动词，而不是名词。像fusionCreatures这样的具有fusionCreatures1方法的类是不清楚的。类似QuxesSolver.minimize(creatures)的东西使意图更加明显。在

---

至于我上面提供的解决方案，还有其他一些技巧值得考虑以加快速度。一个是memoization，它可以帮助避免重复的工作（任何给定的列表都将产生相同的最小长度，因此我们只需将此计算存储在dict中，如果我们再次看到它，就把它吐出来）。如果我们的长度达到1，这是我们在全局范围内所能做的最好的，所以我们可以跳过其余的搜索。在

这是一个完整的运行程序，包括翻译成Python的线性解决方案（同样，请参考博客文章了解它的工作原理）：

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)

输出：

['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

Answer 3

这是我对这个问题的尝试

请在评论中找到描述

inputs = [['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'],]


def fuse_quxes(inp):
    RGB_set = {"R", "G", "B"}

    merge_index = -1
    ## pair qux with next in line and loop through all pairs
    for i, (q1, q2) in enumerate(zip(inp[:-1], inp[1:])):
        merged = RGB_set-{q1,q2}

        ## If more than item remained in merged after removing q1 and q2 qux can't fuse
        if(len(merged))==1:
            merged = merged.pop()
            merge_index=i
            merged_color = merged

            ## loop through the pair until result of fuse is different from qux in either right
            ## or left side 
            if (i>0 and merged!=inp[i-1]) or ((i+2)<len(inp) and merged!=inp[i+2]):
                break

    print(inp)
    ## merge two qux which results to qux differnt from either its right or left else do any
    ## possible merge
    if merge_index>=0:
        del inp[merge_index]
        inp[merge_index] = merged_color
        return fuse_quxes(inp)

    else:
        ## if merge can't be made break the recurssion
        print("Result", len(inp))
        print("_______________________")

        return len(inp)


[fuse_quxes(inp) for inp in inputs]

输出

^{pr2}$