CODEWITHSUNDEEP
python-3.xrecursionpermutation
Andrew
Andrew

Reputation: 65

permutation of a list of numbers done recursively in python

So basically I'm trying to take a list of numbers and write a recursive function that outputs all possible outputs in a list of lists.

My code:

def permutations(lst):
    if len(lst) <= 1:
        return lst
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remlst = lst[:i] + lst[i+1:]
        for p in permutations(remlst):
            l.append([m] + p)
        return l

I'm getting a few errors about not being able to append int.

Simple output:

>>>permutations([1,2])
[[1,2],[2,1]]

Upvotes: 1

Views: 2559

Answers (2)

matz
matz

Reputation: 656

There is an implementation for that in itertools:

import itertools
for p in itertools.permutations(list):
   # do stuff

Also, to fix your own function, notice that in your "base case" len(lst) <= 1 your returning a list, instead of a list-of-lists. Also, the second return statement should be moved out of the loop;

def permutations(lst):
    if len(lst) <= 1:
        return [lst]
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remlst = lst[:i] + lst[i+1:]
        for p in permutations(remlst):
            l.append([m] + p)
    return l

Upvotes: 3

Steven Summers
Steven Summers

Reputation: 5384

Because you iterate through result of permutations

for p in permutations(remlst):

your base case needs to return a list of lists like your recursive case does, otherwise you get the error TypeError: can only concatenate list (not "int") to list

You also need to return after the outer for loop.

def permutations(lst):
    if len(lst) <= 1:
        return [lst] # [[X]]
    l = []
    for i in range(len(lst)):
        m = lst[i]
        remlst = lst[:i] + lst[i+1:]
        for p in permutations(remlst):
            l.append([m] + p)
    return l # return at end of outer for loop

Upvotes: 0

Related Questions