Skip to main content
 首页 » 编程设计

python之使用Python递归进行日常编码挑战

2024年11月01日15Free-Thinker

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

有人可以指出我在此递归代码中犯的错误吗?或者也许可以指导我解决问题?

我知道为什么我的代码会中断,但是我不知道如何解决Python中的“按对象引用传递”问题,我认为这会给我带来更大的问题。

编码问题是:


  在一个神秘的小岛上,有被称为Quxes的生物以三种颜色出现:红色,绿色和蓝色。 Qux的一项功能是,如果其中两个彼此并排站立,它们可以转变为具有第三种颜色的单个生物。
  
  给定N个Quxes排成一行,请确定在进行此类转换的任何可能序列后剩余的数量最少。
  例如,给定输入['R', 'G', 'B', 'G', 'B'],可以通过以下步骤最终得到一个Qux:

        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 


测试数组(除最后一个数组外,其他所有数组均有效):

t1 = fusionCreatures(['R','G','B','G','B']) 
t2 = fusionCreatures(['R','G','B','R','G','B']) 
t3 = fusionCreatures(['R','R','G','B','G','B']) 
t4 = fusionCreatures(['G','R','B','R','G']) 
t5 = fusionCreatures(['G','R','B','R','G','R','G']) 
t6 = fusionCreatures(['R','R','R','R','R']) 
t7 = fusionCreatures(['R', 'R', 'R', 'G', 'G', 'G', 'B', 'B', 'B']) 
 
print(t1.fusionCreatures1()) 
print(t2.fusionCreatures1()) 
print(t3.fusionCreatures1()) 
print(t4.fusionCreatures1()) 
print(t5.fusionCreatures1()) 
print(t6.fusionCreatures1()) 
print(t7.fusionCreatures1()) 

请您参考如下方法:

我将首先提到在O(n)中有一种演绎方法,该方法在blog post中有详细介绍。归结为检查列表中三种类型元素的计数的奇偶性,以确定发生一些固定结果中的哪一个。

您提到您更喜欢使用递归方法,即O(n!)。这是一个好的开始,因为它可以用作帮助获得O(n)解决方案的工具,并且是一种常见的递归模式。

因为我们不知道两个Qux之间的给定融合是否最终会导致最佳的全局解决方案,所以我们不得不尝试各种可能性。我们通过遍历列表并寻找潜在的融合来做到这一点。找到一个后,在新列表中执行转换并在其上调用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.ans。特别是 self.value的名字不好用,很难追踪。似乎打算将其用作参考副本以将 arr重置为其默认值,但是 arr = self.value意味着当 fus_arr在 fusion()中发生突变时, self.value也是如此。几乎所有内容都引用了一个基础列表。

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

self.ans也是不清楚和不必要的;最好将结果值保留在递归函数中的局部变量中。

似乎没有必要将无状态函数放入类中,除非它是纯静态方法并且该类充当名称空间。
造成认知超负荷的另一个原因是分支语句,例如 if和 break。我们想要最小化它们的频率和嵌套。这是伪代码中的 fusionCreatures1,带有突变和复杂交互的注释:

def fusionCreatures1(): 
    if ... 
        read mutated global state 
    for i in len(arr): 
        if complex length and index checks: 
            break 
        if arr[i] != arr[i+ 1]: 
            impure_func_that_changes_arr_length(arr) 
            recurse() 
            if new best compared to global state: 
                mutate global state 


您可能会同意,在头脑上逐步运行此功能非常困难。
在 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或 testlen,因此其意图尚不清楚。

一个好的 linter会选取这些未使用的变量,并找出我提到的大多数其他复杂性问题。
在循环遍历列表时对其进行突变通常是灾难性的。 self.fusion(arr, i)会在循环内对 arr进行突变,这使得很难推断其长度,并且当 range(len(arr))不再与函数主体中的实际 len(arr)匹配时(或至少需要使用-身体前提)。如上所述,使用切片使 self.fusion(arr, i)纯净,可以解决此问题,但显示没有递归 base case,从而导致堆栈溢出错误。
除非上下文很明显,否则避免使用变量名称,例如 arr, arr1, value。同样,这些混淆了意图并使程序难以理解。


一些次要的风格建议:


每个 PEP-8使用 snake_case。类名应为 TitleCased,以区别于功能。无需从 object继承-这是隐式的。
在函数和运算符之间使用一致的间距:例如, range (0,len(arr)-1):更清晰地表示为 range(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