在Python中生成列表长度为k的所有排列的递归算法

Question

以下是我的想法：

对于列表中的每个元素，我可以删除它，然后要求递归函数返回长度k-1的所有排列，然后将删除的数字添加到每个排列中。然后对列表中的所有数字重复此过程。

基本情况是列表为空或只包含一个元素。在这些情况下，我只返回列表。也就是说，只要k小于或等于列表的长度（例如，如果k是3，但是L=[1,2]，我就不能产生任何长度排列k)。

def permutations(l, k):
w = len(l)
if (k <= w): # list is bigger than the length each permutations
    if (w <= 1):
        return list(l)
    else:
        result = []
        for element in l:
            listSmaller = l[:element] + l[element+1:]
            for perm in permutations(listSmaller, k-1):
                result.append([perm] + element)
        return result      
else: # list is not bigger than the length of the permutations, impossible.
    print("k cannot exceed length of list")

我应该如何修改这个？

Answer 1

有两个问题：

首先:[perm]+element在这里，您将向整数添加一个列表。

第二:listsmower=L[:element]+L[element+1:]这里需要一个索引来访问列表的元素。您当前将这些元素用作索引，因此将获得indexerror，因为当element=4时，element+1将为5，但您没有L[4+1:]。

for i, element in enumerate(l):
    listSmaller = l[:i] + l[i+1:]

    for perm in permutations(listSmaller, k-1):
        result.append([perm] + [element])