递归列表构建：所有长度的排列

Question

我在递归方面遇到了一些麻烦，尤其是在列表方面。我不太了解 'building a list recursively' 的过程，因为我不太了解列表的创建位置。我已经得到这个程序来打印出 len(string) 的所有排列，但我想扩展它以便它也能给我长度为 1 到 len(string) - 1 的排列。这是我得到的：

def subset(string):
    result = []

    if len(string) == 0:
        result.append(string)
        return result
    else:
        for i in range(len(string)):
            shorterstring = string[ :i] + string[i+1: ]

            shortersets = subset(shorterstring)

            for s in shortersets:
                result.append(string[i] + s)
    return result

给出：

print(subset("rum"))
['rum', 'rmu', 'urm', 'umr', 'mru', 'mur']

我不明白为什么当我将 result.append(string[i] + s) 更改为 result.append(s) 时，我根本没有输出。

Answer 1

如果将 result.append(string[i] + s) 更改为 result.append(s)，当 len(string) == 0.[=19= 时，您的代码只会添加长度为 len(string) 至 results 的排列]

对于生成所有排列的代码，最后一个 for 循环需要是：

for s in shortersets:
    result.append(string[i] + s)
    result.append(s)

请注意，当与原始代码一起使用时，您实际上最终会向最终输出添加相同排列的多个实例。您可以通过将 results 设为 set 而不是 list 来解决此问题，但您可能想尝试重写代码以完全避免这种低效率。

递归列表构建：所有长度的排列

Recursive list building: permutations of all lengths

python

recursion