All combinations of a complex list

Question

I want to find all possible combinations from the following list:

data = ['a','b','c','d'] 

I know this looks simple, and this can be achieved with the following code:

 comb = [c for i in range(1, len(data)+1) for c in combinations(data, i)] 

but what I want is actually a way to provide each element of the data list with two possibilities ( 'a' or '-a' ).

Examples of combinations may be ['a','b'] , ['-a','b'] , ['a','b','-c'] , etc. without something like the following case ['-a','a'] .

Answer 1

You can write a generator function that takes a sequence and gives every possible combination of negatives. Like this:

 import itertools def negations(seq): for prefixes in itertools.product(["", "-"], repeat=len(seq)): yield [prefix + value for prefix, value in zip(prefixes, seq)] print list(negations(["a", "b", "c"])) 

Result (spaces modified for clarity):

 [ [ 'a', 'b', 'c'], [ 'a', 'b', '-c'], [ 'a', '-b', 'c'], [ 'a', '-b', '-c'], ['-a', 'b', 'c'], ['-a', 'b', '-c'], ['-a', '-b', 'c'], ['-a', '-b', '-c'] ] 

You can integrate this into your existing code with something like

 comb = [x for i in range(1, len(data)+1) for c in combinations(data, i) for x in negations(c)] 

Answer 2

When you have generated regular combinations, you can take a second pass to generate those that have a negation. I would think of it as a binary number, and the number of elements in your list is the number of bits. Count from 0b0000 to 0b1111 through 0b0001, 0b0010, etc., And wherever the bit is set, negate this element as a result. This will create 2 ^ n combinations for each input combination of length n.

Answer 3

Here is one liner, but it can be difficult to follow with it:

 from itertools import product comb = [sum(t, []) for t in product(*[([x], ['-' + x], []) for x in data])] 

The first data card is in the lists of what they can become in the results. Then take product* to get all the features. Finally, smooth each combination with sum .

Answer 4

My solution basically has the same idea as John Zwink's answer . Once you have created a list of all combinations

 comb = [c for i in range(1, len(data)+1) for c in combinations(data, i)] 

you create all possible positive / negative combinations for each comb element. I do this by repeating the entire number of combinations 2**(N-1) and treating it as a binary number, where each binary digit denotes the sign of one element. (For example, a two-element list will have 4 possible combinations, from 0 to 3, represented by 0b00 => (+,+) , 0b01 => (-,+) , 0b10 => (+,-) and 0b11 => (-,-) .)

 def twocombinations(it): sign = lambda c, i: "-" if c & 2**i else "" l = list(it) if len(l) < 1: return # for each possible combination, make a tuple with the appropriate # sign before each element for c in range(2**(len(l) - 1)): yield tuple(sign(c, i) + el for i, el in enumerate(l)) 

Now we apply this function to each element of comb and smooth the resulting nested iterator:

 l = itertools.chain.from_iterable(map(twocombinations, comb))