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

Question

我想创建一个递归算法，它将生成一个长度为n的整数列表的指定长度的所有排列。

以下是我的想法：

对于列表中的每个元素，我可以删除它，然后让我的递归函数向我返回长度为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")

我一直在接受TypeError: can only concatenate list (not "int") to list

我该怎么修改呢？

Answer 1

有两个问题：

首先：[perm] + element这里是一个整数列表。

第二：listSmaller = 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])

Answer 2

在python中，使用时

for a in b:

'a'实际上不是一个可以用作索引的数字，而是一个指向列表'b'中实际元素的指针。换句话说，如果我有以下列表

b = ["Bob", "Jim", "Jane"]

然后在第一次迭代'a'将等于“Bob”，而不是0。

如果要生成索引号而不是指向元素的指针，可以使用：

for a in range(0, len(b)):

代替。使用它，您的代码应该可以工作。

EG

for element in range(0, len(l)):
    listSmaller = l[:element] + l[element+1:]
    for perm in permutations(listSmaller, k-1):
        result.append([perm] + element)
return result