时间戳

首页 > 解决方案 > 在递归函数中返回列表列表

python-3.x - 在递归函数中返回列表列表

问题描述

我正在尝试解决我在 Leetcode 上发现的问题，我需要计算给定字符集的长度r的所有组合。我设法确定了算法，嗯，几乎。

我很难让我的递归函数以列表的形式返回输出。

这是功能。

chrs = ['A', 'B', 'C', 'D', 'E', 'F']

# MY CODE TO PRODUCE SUCH COMBINATIONS
def combination(combn, r, chrset):

    if len(combn)==r:
            return combn

    res = []

    if r - len(combn) <= len(chrset):  # A KIND OF OPTIMIZATION TO CUT DOWN IF WE KNOW FOR SURE THE FINAL LENGTH CAN NEVER BE = R

        for idx,chr in enumerate(chrset):
            combn+=chr
            res += combination(combn, r, chrset[idx+1:])
            combn=combn[:len(combn)-1]
    return [res]

r=5
idx=0
result = combination('', r, chrs)
print("MY CODE")
print(result)

这是输出

MY CODE
[[[[[['A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'F'], ['A', 'B', 'C', 'E', 'F'], []], [['A', 'B', 'D', 'E', 'F'], []], [], []], [[['A', 'C', 'D', 'E', 'F'], []], [], []], [], [], []], [[[['B', 'C', 'D', 'E', 'F'], []], [], []], [], [], []], [], [], [], []]]

我想要的是作为输出

[['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'C', 'D', 'F'], ['A', 'B', 'C', 'E', 'F'], ['A', 'B', 'D', 'E', 'F'], ['A', 'C', 'D', 'E', 'F'], ['B', 'C', 'D', 'E', 'F']]

我尝试了几种组合，但不知何故它总是最终成为一个嵌套列表（一些组合总是一个列表中的列表中的列表中的列表中的列表......）

我不想在我的函数之外处理这样的输出，而是想了解一些有效的技术来确保递归不会导致这样的模式。

编辑

我知道其他用户可能已经以另一种方式提出了这个问题，并且我知道一旦这种解决方法使用浅拷贝 combn [:] 就可以解决这个问题。我想避免这种情况，因为这是一项昂贵的操作（就空间而言，我猜也是时间）。

def combination(combn, r, chrset, final_result):

    if len(combn)==r:
            final_result.append(combn[:])
            return final_result
    if r - len(combn) <= len(chrset):  # A KIND OF OPTIMIZATION TO CUT DOWN IF WE KNOW FOR SURE THE FINAL LENGTH CAN NEVER BE = R

        for idx, chr in enumerate(chrset):
            combn.append(chr)
            combination(combn, r, chrset[idx + 1:], final_result)
            combn.pop()

    return final_result

r=5
idx=0
result = combination([], r, chrs, [])
print("MY CODE")
print(result)

标签： python-3.xlistrecursion

解决方案

也许您可以考虑不使用 enumerate 并使用实现回溯的单独帮助函数：

def helper(start, chrs, r, comb, combinations):
    if len(comb) == r:
        combinations.append(comb.copy())
    for i in range(start, len(chrs)):
        comb.append(chrs[i])
        helper(i + 1, chrs, r, comb, combinations)
        comb.pop()
    
def get_combinations(chrs, r):
    combinations = []
    helper(0, chrs, r, [], combinations)
    return combinations

chrs = ['A', 'B', 'C', 'D', 'E', 'F']
r = 5
combinations = get_combinations(chrs, r)
print(combinations)

输出：

[['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'C', 'D', 'F'], ['A', 'B', 'C', 'E', 'F'], ['A', 'B', 'D', 'E', 'F'], ['A', 'C', 'D', 'E', 'F'], ['B', 'C', 'D', 'E', 'F']]

推荐阅读