Generate all permutations of all lengths

Question

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

Coeternity

Is this homework? If so, please tag it as such, and consider posting a little more about the progress you've made so far. – Optimum

This was not homework, sorry for not saying or posting other wise. – Coeternity

Answer 1

I think that would be all permutations of each subset.

The easiest way to return subsets is to consider all binary integers from 0 (the empty set) through the length of your input list (the complete set). So you count from 0 through and including 2**(length(input)) and use the results to mask off all elements to exclude from that particular subset.

From there you should be able to use any of the many examples of code out on the 'net for returning permutations.

Ringleader

Incidentally in Python the itertools module has a function which generates permutations and I've created an ugly one-liner to return all subsets using a generator expression. However it's too hideous to post here. – Ringleader

Answer 2

I'd suggest starting with something simpler. Suppose l is a list with n elements. First, can you write a function to generate all permutations of l which have a fixed length k? Then, can you find a way to call that function repeatedly with different k values to generate the permutations of length 0, all permutations of length 1, all permutations of length 2, and so on until you get to n?

Optimum

Answer 3

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.

Brandenburg

Answer 4

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.

Ringleader

Answer 5

In general a list of length n has n! arrangements or permutations. So with multiple lengths, we would have n!(n-k)! where k is 0 < k < n.

Lunkhead

Please don't post full code for questions which are homework/interview problems, but instead offer suggestions of directions in which to go. – Variolous

Answer 6

for a list of columns feature_cols, we can use this one liner:

[combo for i in range(1, len(feature_cols) + 1) for combo in itertools.combinations(feature_cols, i) ]

which is basically doing:

all_combinations = []
for i in range(1, len(feature_cols) + 1):
    for combo in itertools.combinations(feature_cols, i):
        all_combinations.append(combo)

e.g.

>>> feature_columns = ['TV', 'Radio', 'Newspaper']
>>> all_combinations = [combo for i in range(1, len(feature_cols) + 1) for combo in itertools.combinations(feature_cols, i) ]
>>> all_combinations
[('TV',),
 ('Radio',),
 ('Newspaper',),
 ('TV', 'Radio'),
 ('TV', 'Newspaper'),
 ('Radio', 'Newspaper'),
 ('TV', 'Radio', 'Newspaper')]

Unchain