找到2 ^元素的n -2個組合在一個列表

我有以下列表：找到2 ^元素的n -2個組合在一個列表

list1 = ['g1','g2','g3','g4']

我想找到2^n-2組合，其中n是列表中的項目的總數。對於n = 4，結果應該是2^4 -2 = 14，即14個組合。

的組合方式如下：

[[['g1'],['g2','g3','g4']],[['g2'],['g1','g3','g4']], [['g3'],['g1','g2','g4']],['g4'],['g1','g2','g3']],[['g1','g2'],['g3','g4']],[['g1','g3'],['g2','g4']],[['g1','g4'],['g3','g4']],[['g2','g3'],['g1','g4']], 
[['g2','g4'],['g1','g3']],[['g3','g4'],['g1','g2']],[['g1','g2','g3'],['g4']],[['g2','g3','g4'],['g1']],[['g3','g4','g1'],['g2']],[['g4','g1','g2'],['g3']]]

我知道一種方法：在第一次迭代中採取單個元件，並把它放入一個列表和第二列表的其它元素：['g1'],['g2','g3','g4'] 在第二次迭代中採取在一個2種元素列表和第二列表中的其他元素。 ['g1','g2'],['g1','g4'] 有沒有其他方法？我正在用python編寫這個程序。我的方法是昂貴的。有沒有任何庫方法可以快速執行此操作。

來源

2016-11-18 Sourasekhar Banerjee

你是什麼意思的代價？無論實現如何，生成組合的算法複雜度都是指數級的。 – hyades

我更新了我的答案，以更好地反映您的要求。 –

下面是使用itertools

import itertools as iter 

list1 = ['g1', 'g2', 'g3', 'g4'] 
combinations = [iter.combinations(list1, n) for n in range(1, len(list1))] 
flat_combinations = iter.chain.from_iterable(combinations) 
result = map(lambda x: [list(x), list(set(list1) - set(x))], flat_combinations) 
# [[['g1'], ['g4', 'g3', 'g2']], [['g2'], ['g4', 'g3', 'g1']], [['g3'], ['g4', 'g2', 'g1']],... 
len(result) 
# 14

來源

2016-11-18 06:52:15

你如何得到元組的第二部分？ – hyades

我不完全確定這是從輕微混淆的問題需要。他在組合之後，這只是元組的第一部分。 –

OP的例子是一個有2個部分的有序集合分區的列表。這隻會生成每個分區的一半。您需要將每個子集/組合與其補碼進行配對。 –

itertools.combinations（可迭代，R）

從輸入可迭代元件的返回ř長度子序列的功能性的方法。組合按字典順序排列。所以，如果輸入可迭代排序，組合元組將按排序的順序生成。

from itertools import combinations 
list1 = ['g1','g2','g3','g4'] 
for n in range(1,len(list1)): 
    for i in combinations(list1,n): 
     print(set(i), set(list1) - set(i))

出來：

{'g1'} {'g2', 'g3', 'g4'} 
{'g2'} {'g1', 'g3', 'g4'} 
{'g3'} {'g1', 'g2', 'g4'} 
{'g4'} {'g1', 'g2', 'g3'} 
{'g1', 'g2'} {'g3', 'g4'} 
{'g1', 'g3'} {'g2', 'g4'} 
{'g1', 'g4'} {'g2', 'g3'} 
{'g2', 'g3'} {'g1', 'g4'} 
{'g2', 'g4'} {'g1', 'g3'} 
{'g3', 'g4'} {'g1', 'g2'} 
{'g1', 'g2', 'g3'} {'g4'} 
{'g1', 'g2', 'g4'} {'g3'} 
{'g1', 'g3', 'g4'} {'g2'} 
{'g2', 'g3', 'g4'} {'g1'}

你可以試試這個

來源

2016-11-18 07:07:47

這與我的回答非常相似，並沒有考慮到OP希望所有長度爲1的組合都到'len（list1）'。 –

只是在它上面，這很簡單 –

看到我的問題的操作。在這裏，我不需要所有的nC2元素，我需要的是第一個元素在一個列表或元組中，第二個列表或元組中的其他元素。（'g1'，'g2'），（'g3'，'g4'）等等（'g1'），（'g2'，'g3'，'g4'）等 –

我想從中國編碼器（我猜）的解決方案。這是我自己的解決方案：

import itertools 


def flatten(*z): 
    return z 


list1 = ['g1','g2','g3','g4'] 

sublists = [] 
for i in range(1, len(list1)): 
    sublists.extend(itertools.combinations(list1, i)) 

pairs = [] 
for a, b in itertools.product(sublists, sublists): 
    if len(a) + len(b) == len(list1) and \ 
    len(set(flatten(*a, *b))) == len(list1): 
     pairs.append((a, b)) 

print(pairs, len(pairs))

來源

2016-11-18 07:54:18

既然你把powerset（減去空集和整集）作爲一個列表來實現，那麼你可以用它自己的相反的方式將其拉鍊：比如'pairs = list（zip（sublists，reversed（sublists）））'而不是使用'itertools.product'和過濾。 –

這很酷使用反轉和拉鍊！ –

找到2 ^元素的n -2個組合在一個列表

回答

相關問題