Recursive Algorithm To Generate All Permutations Of Length K Of A List In Python

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. Following is my idea: For every element

Solution 1:

# code takes list lst andint n denoting length of permutation
# returnsall permutations of length n over items in lst  
def Perm(lst,n):
    # if length of permutation is negative or0, returnempty
    if n<=0:
        return [[]]
    # else take empty list l 
    l=[]
    # loop over whole lst
    for i inrange(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
        # recursivecallto 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 2over 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 2over 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]]

Solution 2:

There are two problems:

First: [perm] + element Here you are adding a list to an integer.

Second: listSmaller = l[:element] + l[element+1:] Here you need an index to access the elements of the list. You are currently using the elements as an index and will therefore get an IndexError because when element=4, element+1 will be 5 but you do not have l[4+1:].

---

Your code works when I do the following changes in your code. I am only showing the modified lines. I am not sure if the output is as expected. You can try it and let me know.

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

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

Solution 3:

In python, when using

for a in b:

'a' is not actually a number which can be used as an index, but is instead a pointer to an actual element in list 'b'. Put another way, if I had the following list

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

Then on the first iteration 'a' would be equal to "Bob", and not 0.

When you want to generate index numbers instead of pointers to elements, you can use:

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

instead. Using this, your code should then work.

e.g.

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