在 Python 中生成列表长度 k 的所有排列的递归算法 [英] Recursive Algorithm to generate all permutations of length k of a list in Python

问题描述

我想创建一个递归算法来生成所有排列指定长度的整数列表的长度 n.

I want to create a recursive algorithm that will generate all permutations of a specified length of a list of integers with some length n.

以下是我的想法:

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

For every element in the list, I can remove it, then ask my recursive function to return to me all permutations of length k-1, and then to each of those permutations I will add the removed number. Then repeat this process for all numbers in the list.

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

The base cases are when the list is empty or contains only one element. In these cases I just return the list. That is, as long as k is less than or equal to the length of the list (ex. if k is 3, but l = [1,2], I can't produce any permutations of length 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

我应该如何修改?

推荐答案

# code takes list lst and int n denoting length of permutation
# returns all permutations of length n over items in lst  
def Perm(lst,n):
    # if length of permutation is negative or 0, return empty
    if n<=0:
        return [[]]
    # else take empty list l 
    l=[]
    # loop over whole lst
    for i in range(0,len(lst)): 
        m=lst[i] # current element of lst (ith) 
        remLst=lst[:i] + lst[i+1:]  # remaining list i.e. all elements except ith
        # recursive call to Perm with remaining list and decremented length 
        for p in Perm(remLst,n-1): 
            # append current element + all sublists p generated through recursion as an item in list l
            l.append([m]+p) 
    return l

# some examples 
# all permutations of length 2 over characters A,B,C
print(Perm(['A','B','C'],2))
# output: [['A', 'B'], ['A', 'C'], ['B', 'A'], ['B', 'C'], ['C', 'A'], ['C', 'B']]

# all permutations of length 2 over characters 1,2,3,4
print(Perm([1,2,3,4],2))
# output: [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]

这篇关于在 Python 中生成列表长度 k 的所有排列的递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！