все комбинации сложного списка

Я хочу найти все возможные комбинации из следующего списка: 

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

Я знаю, что это выглядит простой задачей, и она может быть достигнута с помощью следующего кода: 

comb = [c for i in range(1, len(data)+1) for c in combinations(data, i)]
Но на самом деле я хочу, чтобы каждый элемент списка данных имел две возможности ('a' или '-a').

Примером таких комбинаций может быть ['a','b'] , ['-a','b'], ['a','b','-c'], и т.д. без чего-то вроде следующего случая, конечно ['-a','a'].

4 5
python combinatorics

4 ответа:

Можно написать функцию-генератор, которая принимает последовательность и выдает каждую возможную комбинацию отрицаний. Вот так: 

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

Результат (пробел изменен для ясности): 

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

Вы можете интегрировать это в существующий код с помощью чего-то вроде

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

После того, как вы сгенерировали регулярные комбинации, вы можете сделать второй проход, чтобы сгенерировать те, которые имеют "отрицание.- Я бы сказал, что это двоичное число, а число элементов в вашем списке-это число битов. Считайте от 0b0000 до 0b1111 через 0b0001, 0b0010 и т. д., и где бы ни был установлен бит, отрицайте этот элемент в результате. Это даст 2^n комбинаций для каждой входной комбинации длины n.

3

Вот один лайнер, но его может быть трудно проследить: 

from itertools import product

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

Первая карта data к спискам того, чем они могут стать в результатах. Затем возьмите product*, чтобы получить все возможности. Наконец, сгладьте каждую комбинацию с помощью sum.

3

Мое решение в принципе имеет такое же представление как ответ Джон Zwinck по. После того, как вы произвели список всех комбинаций 

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

Вы генерируете все возможные положительные/отрицательные комбинации для каждого элемента comb. Я делаю это, повторяя общее число комбинаций, 2**(N-1), и рассматривая его как двоичное число, где каждая двоичная цифра обозначает знак одного элемента. (Например, двухэлементный список будет иметь 4 возможных комбинации, от 0 до 3, представленные следующим образом: 0b00 => (+,+), 0b01 => (-,+), 0b10 => (+,-) и 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))
Теперь мы применяем эту функцию к каждому элементу comb и выравниваем полученный вложенный итератор: 
l = itertools.chain.from_iterable(map(twocombinations, comb))
0