时间戳

首页 > 解决方案 > 使用递归找到大小为 k 的平衡代码

python - 使用递归找到大小为 k 的平衡代码

问题描述

我正在处理的作业有一个问题，我必须在 python 中编写一个递归函数，它返回 size 的平衡代码k，它被定义为2k包含相等数量0s的所有长度二进制字符串的列表字符串的每一半。它只允许接受一个参数，k. 到目前为止，我已经找到了一种方法来返回所有可能的二进制字符串的列表 length 2k，但是在将列表减少到仅符合条件的那些时遇到了麻烦。到目前为止，这是我的代码：

def balanced_code(k):  
if k >= 0:        
    if k == 0:
        return ['']
    else:
        L = []
        x = balanced_code(k - 1)
        for i in range(0, len(x)):
            L.append('00' + x[i])                
            L.append('01' + x[i])
            L.append('10' + x[i])
            L.append('11' + x[i])
        return L
else:
    return

我的计划是在 for 循环之后，我会检查每个项目中L提到的标准（0字符串的每一半中 s 的数量相等），但很快意识到这并没有给出正确的结果，因为它会L在每次调用期间减少，并且我只想在对函数的所有调用完成后减少它。有什么方法可以跟踪代码所在的递归级别或类似的东西，以便我只在所有调用完成后才减少列表？

标签： pythonalgorithmrecursionbinary

解决方案

您可以通过在 k-1 结果的每一侧添加“0”和“1”位来接近递归。这些位需要最后添加到右侧和左侧的每个位置。由于这将产生重复，使用集合返回字符串将确保不同的结果。

def balancedCodes(k):
    if not k: return {""}
    return { code[:pos]+bit+code[pos:]+bit for code in balancedCodes(k-1)
                                           for pos  in range(k)
                                           for bit  in ("0","1") }

for bc in sorted(balancedCodes(3)): print(bc)


000000
001001
001010
001100
010001
010010
010100
011011
011101
011110
100001
100010
100100
101011
101101
101110
110011
110101
110110
111111

111111 结果是每边都没有零的情况

推荐阅读