1

Whats the best way to generate all combinations of a list, where each combinations contains every item from the list and where you can combine other items.

For example, for a list ['a','b','c'], I like to generate:

['a','b','c']
['ab','c']
['a','bc']
['abc']

I find it a bit similar to: Python: Generating all ordered combinations of a list. But this one only cares about the slices. I want all the combinations that takes every item from the list. Is there a built in function from itertools that can be used to generate the answer?

The list could also be numbers, that could have duplicates values. For example: [1,2,1] should generate:

[1,2,1]
[12,1]
[1,21]
[121]

I could try to use the code from the link, but instead of generating combinations of the items, I would generate the combinations base on the index of the list. Where I take all combinations that start with 0, then look for the next item and look for all combinations that start with that item and so on. I dont think that would be efficient though.

Improve this question

3 Answers 3

Reset to default
2

You can think of two adjacent characters in your string as being either "separated" or "concatenated". Using itertools.product() you can generate all combinations of separated/concatenated between two characters and then use a simple function to generate a list of strings from this information:

import itertools

l = ['a','b','c']

def generate_combination(source, comb):
    res = []
    for x, action in zip(source,comb + (0,)):
        res.append(x)
        if action == 0:
            yield "".join(res)
            res = []

print [list(generate_combination(l,c)) 
       for c in itertools.product((0,1), repeat=len(l)-1)]

This doesn't work for numbers though unless you convert them to strings first.

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

2 Comments

This seems to work fine. Just trying to see how it works.
I just understood your generator function, its pretty cool. Thanks for the answer.
1

Here is additional code to make @acidtobi answer work for both int and char with the help of .isdigit(). 

final = [list(generate_combination(l,c)) 
       for c in itertools.product((0,1), repeat=len(l)-1)]

print [[int(i) if i.isdigit() else i for i in alist ] for alist in final]

So for l = [ 1,2,3] , it will show

>>> 
[[1, 2, 3], [1, 23], [12, 3], [123]]

And for l = ['a','b','c']

>>> 
[['a', 'b', 'c'], ['a', 'bc'], ['ab', 'c'], ['abc']]
Improve this answer

Comments

1 
import numpy as np
l = ['a','b','c','d']
#l = [0,1,2,3]
d = np.arange(2**(len(l)-1))
#create a separator array for all possible combinations
sep = np.where((d[:,None] & (1 << np.arange(len(l))[::-1])) > 0, ',','')
#merge the separator to the strings
merged = np.core.defchararray.add(sep,np.asarray(l,dtype=str)).tolist()
#reformat and split
[''.join(e).split(',') for e in merged]

#works for any characters
[['abcd'],
 ['abc', 'd'],
 ['ab', 'cd'],
 ['ab', 'c', 'd'],
 ['a', 'bcd'],
 ['a', 'bc', 'd'],
 ['a', 'b', 'cd'],
 ['a', 'b', 'c', 'd']]

Out[128]: 
[['0123'],
 ['012', '3'],
 ['01', '23'],
 ['01', '2', '3'],
 ['0', '123'],
 ['0', '12', '3'],
 ['0', '1', '23'],
 ['0', '1', '2', '3']]
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.