Recursive Algorithm to generate all permutations of length k of a list in Python

Question

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 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.

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).

This is what I've written:

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")

I keep getting TypeError: can only concatenate list (not "int") to list

How should I modify this?

if you are trying to make it from scratch this wont help, but have you looked at the python itertools module? docs.python.org/3/library/itertools.html — dangee1705
– dangee1705, Commented Sep 16, 2018 at 16:25
Could you please provide the parameters to permutations which are resulting in the reported error? Thanks! — Mark A. Fitzgerald
– Mark A. Fitzgerald, Commented Sep 16, 2018 at 16:27
When you use for element in l:, the element is no more an index starting from 0 but the individual elements of the list l, one at a time. Now while accessing the elements of the list l you can't use, l[:element] or l[element+1:]. You need an index which you can get using enumerate as for i, element in enumerate(l): and then you can use l[:i] + l[i+1:] — Sheldore
– Sheldore, Commented Sep 16, 2018 at 16:27
Also, perm is a list, so you shouldn’t wrap it with a [ ]. Element is an int so you should wrap it with a [ ] (in the line where you append to result) — Roy Shahaf
– Roy Shahaf, Commented Sep 16, 2018 at 16:30

Shailaja · Accepted Answer · 2019-10-16 00:31:38Z

3

# 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]]

edited Oct 16, 2019 at 0:31

answered Oct 14, 2019 at 9:56

Shailaja

516 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Alessio Over a year ago

While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.

Sheldore · Accepted Answer · 2018-09-16 16:49:22Z

1

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])

answered Sep 16, 2018 at 16:49

Sheldore

39.2k9 gold badges63 silver badges76 bronze badges

Comments

Jake Lawrence · Accepted Answer · 2018-09-16 16:45:44Z

0

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

answered Sep 16, 2018 at 16:45

Jake Lawrence

2961 silver badge9 bronze badges

Collectives™ on Stack Overflow

Recursive Algorithm to generate all permutations of length k of a list in Python

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related