all combination of a complicated list

Question

I want to find all possible combination of the following list:

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

I know it looks a straightforward task and it can be achieved by something like 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 give each element of the list data two possibilities ('a' or '-a').

An example of the combinations can be ['a','b'] , ['-a','b'], ['a','b','-c'], etc. without something like the following case of course ['-a','a'].

Answer 1

You could write a generator function that takes a sequence and yields each possible combination of negations. 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 (whitespace 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

Once you have the regular combinations generated, you can do a second pass to generate the ones with "negation." I'd think of it like a binary number, with the number of elements in your list being the number of bits. Count from 0b0000 to 0b1111 via 0b0001, 0b0010, etc., and wherever a bit is set, negate that element in the result. This will produce 2^n combinations for each input combination of length n.

Answer 3

Here is one-liner, but it can be hard to follow:

from itertools import product

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

First map data to lists of what they can become in results. Then take product* to get all possibilities. Finally, flatten each combination with sum.