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

问题描述 投票:0回答:2

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

以下是我的想法:

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

基本情况是列表为空或仅包含一个元素。在这些情况下,我只是返回列表。也就是说,只要k小于或等于列表的长度(例如,如果k3,但是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

我该怎么修改呢?

python algorithm recursion permutation
2个回答
1
投票

有两个问题:

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

第二:listSmaller = l[:element] + l[element+1:]在这里你需要一个索引来访问列表的元素。你目前正在使用元素作为索引,因此将得到一个IndexError,因为当element=4element+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])

0
投票

在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
© www.soinside.com 2019 - 2024. All rights reserved.