0

I am trying to generate a permutation of list in python with recursion.

import copy

def perm(seq):
    if len(seq) == 1:
        return seq
    else:
        nseq = perm(seq[1:])
        return zip_letter(seq[0], nseq)


def zip_letter(c, seq):
    lis = []
    for i in range(len(seq)+1):
        seq.insert(i, c)
        lis.append(copy.deepcopy(seq))
        seq.pop(i)
    return lis

print perm(['a', 'b', 'c'])

The output is [['a', ['b', 'c'], ['c', 'b']], [['b', 'c'], 'a', ['c', 'b']], [['b', 'c'], ['c', 'b'], 'a']]

which seems fine, but not in correctly inserted format. what am i missing?

manish kumar
  • 31
  • 2
  • 1
    Unless you are deliberately rewriting it yourself as an exercise, you should instead use [`itertools.permutations`](https://docs.python.org/2/library/itertools.html#itertools.permutations). – BrenBarn Feb 16 '15 at 20:55

1 Answers1

3

I would recommend using the existing function in itertools

>>> list(itertools.permutations(['a', 'b', 'c']))
[('a', 'b', 'c'),
 ('a', 'c', 'b'),
 ('b', 'a', 'c'),
 ('b', 'c', 'a'),
 ('c', 'a', 'b'),
 ('c', 'b', 'a')]
Cory Kramer
  • 114,268
  • 16
  • 167
  • 218
  • I like `itertools` too, but this doesn't explain how to generate a permutation with recursion or point out the bug in the OP's code.. – DSM Feb 16 '15 at 20:59
  • I want to use recursion. Not an existing library – manish kumar Feb 16 '15 at 21:41
  • @manishkumar: In that case, you should have _explicitly_ stated in your question that you know about `itertools.permutations` but that you are doing it this way in order to learn about recursion. But your question probably would have still been closed, as there are good examples of recursion in the dupe link that's been add to your question. Also see [Python recursion permutations](http://stackoverflow.com/questions/13109274/python-recursion-permutations). – PM 2Ring Feb 17 '15 at 07:21
  • @manishkumar: FWIW, it's best to avoid recursion in Python, unless you _really_ need it. Python doesn't have [tail call](http://en.wikipedia.org/wiki/Tail_call) optimization, and there's a limit on recursion depth (although that can be modified). So recursion in Python is generally inefficient (compared to languages that do provide tail call optimization). You may also be interested in iterative code that can produce [individual permutations given an index number](http://stackoverflow.com/a/28525468/4014959). – PM 2Ring Feb 17 '15 at 07:24
  • Thanks for your answer. Still, it will be great if you can tell me what am i missing in my code? – manish kumar Feb 17 '15 at 17:16