permutation of a list of numbers done recursively in python

Question

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

give us a stacktrace :)

parsethis
– parsethis

2017-03-14 02:22:02 +00:00
Commented Mar 14, 2017 at 2:22 — parsethis
– parsethis, Commented Mar 14, 2017 at 2:22

matz · Accepted Answer · 2017-03-14 02:31:50Z

3

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

edited Mar 14, 2017 at 2:31

answered Mar 14, 2017 at 2:22

matz

6566 silver badges19 bronze badges

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

Comments

Steven Summers · Accepted Answer · 2017-03-14 02:31:05Z

0

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

answered Mar 14, 2017 at 2:31

Steven Summers

5,4242 gold badges24 silver badges33 bronze badges

Collectives™ on Stack Overflow

permutation of a list of numbers done recursively in python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related