CODEWITHSUNDEEP
pythonlistcombinations
user1179317
user1179317

Reputation: 2903

Generate all ordered combinations of a list, where each combination includes all items

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.

Upvotes: 1

Views: 783

Answers (3)

Allen Qin
Allen Qin

Reputation: 19947

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']]

Upvotes: 1

Anil_M
Anil_M

Reputation: 11453

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']]

Upvotes: 1

acidtobi
acidtobi

Reputation: 1365

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.

Upvotes: 2

Related Questions