Alex Rivera | Logout

Generate all permutations of all lengths

Asked 2010-11-02T04:51:03.500
20

How would you generate all the possible permutations of list b(1,6,8,3,9,5) including ones of different length? Example:

List a = [1,2,3]
generateperms(a)
1,2,3
3,1,2
3,2,1
1,3,2
2,1,3
2,3,1
2,3
1,2
1,3
2,1
3,2
3,1

And so forth and getting all the permutarions of each length?

EDIT: I'm just going to use this, written in python, works well enough:

import itertools  
a = ['a','b','c']  
for i in range(len(a)):  
    print list(itertools.permutations(a,i+1))
permutation
Edit
Report

2 Answers

1

Consider the recursive implementation of generating all permutations of a string. If you store the sub-permutations as you build them up, then you'll have all the ones you want.

In erlang, as a starting point (which is a modified version of 3.3 Permutations)

perms([]) -> [[]];
perms(L) ->
  [ [H|T] || H <- L, T <- perms(L -- [H])]
  ++ [ [T] || H <- L, T <- perms(L -- [H]) ].

but note that this leaves you with duplicates and lots of arrays of empty arrays that you'll have to remove to make the output prettier.

answered 2010-11-02T05:11:25.080
1

Earlier I mentioned that I concocted, in Python, a hideous lambda expression to generate all subsets of a sequence using the bin() integer to binary string built-in function that they added in 2.6.

Here's the uglier version of it:

subsets = lambda s: (
    (s[x] for x,c in 
       enumerate("0" * (len(s)-len(bin(i)[2:])) + bin(i)[2:])
       if int(c)) 
     for i in range(0,2**len(s)
     )
)

But I noticed that I can replace the "0" * ... +" portion of that expression with a simple call to the string's zfill() method (thanks SO User: gimel). So that becomes the slightly less odious:

subsets = lambda s: (
        [s[x] for x,c in 
              enumerate(bin(i)[2:].zfill(len(s)))
              if int(c)
              ]
        for i in range(0,2**len(s))
    )

This, despite its appearances, is a relatively simple implementation of what I described: given the binary string representing any integer from zero to the size of our set, mask out any of the elements corresponding to zeros in our binary string. That's the inner list comprehension. The outer (generator) expression simply covers the necessary range.

The OP's approach of using itertools.permutations() with two arguments is more elegant. I might have thought of it if I'd known to look at the __doc__ string for that function. However, I did have to spend a little time convincing myself that both approaches give the same results.

answered 2010-11-04T03:34:16.223

Your Answer