-3

Possible Duplicate:
How to generate all permutations of a list in Python

I am given a list [1,2,3] and the task is to create all the possible permutations of this list.

Expected output:

[[1, 2, 3], [1, 3, 2], [2, 3, 1], [2, 1, 3], [3, 1, 2], [3, 2, 1]]

I can't even think from where to begin. Can anyone help?

Thanks

Community
  • 1
  • 1
HussainNagri
  • 45
  • 2
  • 7

2 Answers2

3

itertools.permutations does this for you.

Otherwise, a simple method consist in finding the permutations recursively: you successively select the first element of the output, then ask your function to find all the permutations of the remaining elements.

A slightly different, but similar solution can be found at https://stackoverflow.com/a/104436/42973. It finds all the permutations of the remaining (non-first) elements, and then inserts the first element successively at all the possible locations.

Community
  • 1
  • 1
Eric O. Lebigot
  • 91,433
  • 48
  • 218
  • 260
-1

this is a rudimentary solution... the idea is to use recursion to go through all permutation and reject the non valid permutations. 

    def perm(list_to_perm,perm_l,items,out):
        if len(perm_l) == items:
            out +=[perm_l]
        else:
            for i in list_to_perm:
                if i not in perm_l:
                    perm(list_to_perm,perm_l +[i],items,out)


a = [1,2,3]
out = []
perm(a,[],len(a),out)
print out

output:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
fhtuft
  • 966
  • 5
  • 8
  • This is awfully complicated (long and not very legible). A much simpler solution can be found for instance at http://stackoverflow.com/a/104436/42973. – Eric O. Lebigot May 29 '12 at 07:11
  • @EOL don't think your solution rejects partial solution that will end up as duplicates (backtracking) . So the extra "complexity" gives you much better speed. – fhtuft May 29 '12 at 08:43
  • Thank you for your feedback. I'm not sure I understand this question of duplicates. Are you referring to the case where the input list contains identical elements? like with [0, 0, 1], whose permutations include [0, 0, 1] twice?? Note that including it twice is quite natural; this is what both itertools.permutations() and the solution I linked to do. – Eric O. Lebigot May 29 '12 at 09:11
  • 1
    If you are interested in simplifying this code, you may want to consider submitting this piece of code to codereview.stackexchange.com. For instance, the *six* lines that follow "# find out if i is used" can be written much more simply (and legibly) as `if i not in my_perm_l`. In a nutshell, your Python code looks like C, whereas Python allows programmers to express things much more simply than in C. – Eric O. Lebigot May 29 '12 at 09:16
  • yes I agree it's not to pythonic (It's written to be clear). but I think in a way your solution is wrong (you only do the permutations, not the "pruning" of solutions). run your solution on the problem [1,2,3](you get duplicates). This problem is I believe is a (extremely simple)Combinatorics search problem, and can be solved by backtracking: https://en.wikipedia.org/wiki/Backtracking you won't to reject solution u know don't go anywhere, for speed and correctness(you can remove them from output, but this takes even more time). – fhtuft May 29 '12 at 10:22
  • Right, the solution I linked to does not work. However, I am still not sure what you mean by this duplication. I wrote my own solution (see http://stackoverflow.com/a/10799849/42973), just to show that it possible to write something much simpler than the solution above: maybe you can comment on it here and describe what you mean by duplication? – Eric O. Lebigot May 29 '12 at 13:09
  • Side note: "pythonic" most *often* means "simple, clean and efficient" (instead of complex or idiosyncratic). – Eric O. Lebigot May 29 '12 at 13:43
  • PS: I fixed the solution from the first link I gave (Eli's solution at http://stackoverflow.com/a/104436/42973). You can see from either this solution of mine that there is no need for any pruning. – Eric O. Lebigot May 29 '12 at 13:50
  • sorry, I was not clear on that. it is like, input: [1,2,3] output: [[1,2,3],[1,2,3],[2,1,3,[2,1,3]...] there is now two of [1,2,3] and [2,1,3]. For the test case [1,2,3] there is supposed to be 3!=2*3=6 outputs.I think your solutions give 12 (old) and 9 (new) outputs. run for the test case [1,2,3] and see, my code gives the correct output. the O is also better. But the code can be made more pythonic, I agree on that.I can see if can make it better. – fhtuft May 29 '12 at 14:11
  • I see what you mean. However, both Eli's corrected solution and mine give the correct 6 elements. You can test them easily with `list(all_perms([1, 2, 3]))`. – Eric O. Lebigot May 29 '12 at 14:51
  • I think the new solution u linked to gives 9 elements. – fhtuft May 29 '12 at 15:20
  • If you run the solution (for instance in the way I indicated), you can certainly see that it gives the correct 6 permutations. How did you obtain 9 elements??? – Eric O. Lebigot May 30 '12 at 02:35
  • hi, I got 9 for one of the old buggy (for p in all_perms..) solutions. but now yours work fine. – fhtuft May 31 '12 at 18:42
  • and made my solution a little simpler! – fhtuft May 31 '12 at 19:18