複雜列表的所有組合

我想找到下面的列表中的所有可能的組合：複雜列表的所有組合

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']的下面的情況。

來源

2014-09-04 Ophilia

您可以編寫一個生成器函數，它接受一個序列並生成每個可能的否定組合。就像這樣：

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

來源

2014-09-04 12:20:53 Kevin

非常感謝，正是我想要的:) – Ophilia 2014-09-04 12:35:07

一旦您生成了常規組合，您可以通過第二遍來生成具有「否定」的組合。我想它就像一個二進制數字，列表中的元素數量是位數。通過0b0001,0b0010等從0b0000到0b1111進行計數，並且無論設置了哪個位，都將結果中的該元素取反。對於長度爲n的每個輸入組合，這將產生2^n個組合。

來源

2014-09-04 12:09:55

感謝提示，這真的有幫助 – Ophilia 2014-09-04 12:31:38

我的解決方案主要有同樣的想法如John Zwinck's answer。當你已經產生你生成的comb每個元素的所有可能的正/負組合所有組合

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

名單。我通過遍歷組合的總數2**(N-1)並將其視爲二進制數來完成此操作，其中每個二進制數字表示一個元素的符號。（例如，兩個元素的列表將具有4個可能的組合，0〜3，通過0b00 => (+,+)，，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))

來源

2014-09-04 12:43:50 Carsten

這裏是一個班輪，但它可以是難以遵循：

from itertools import product 

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

第一張地圖data列出他們可以成爲結果的列表。然後以product*獲得所有可能性。最後，用sum平鋪每個組合。

來源

2014-09-04 12:44:18 zch

複雜列表的所有組合

回答

相關問題