列表中不同元組的元素的組合

我有這樣的元組列表：[(1, 2, 3), (2, 4)]（列表的長度和元組可能會有所不同），我想要得到所有包含至少的組合元素列表中的每個元組，而且包含更多的組合。列表中不同元組的元素的組合

所以結果應該是在這個例子中：
[[1, 2, 3, 2, 4], [1, 2, 2, 4], [2, 3, 2, 4], [1, 2, 4], [2, 2, 4], [3, 2, 4], [1, 2, 3, 2], [1, 2, 3, 4], [1, 2, 2], [1, 2, 4], [2, 3, 2], [2, 3, 4], [1, 2], [1, 4], [2, 2], [2, 4], [3, 2], [3, 4]]

最小的結果應該包含等於原始列表元組的一些元素數，最大的一個應該包含存在於元組的所有元素。

元素的順序並不重要，重複應該最終被消除（所以[1, 2, 3, 2, 4] = [1, 2, 3, 4]，應該只在結果中只有一次，類似[3, 2] = [2, 3]等），但我想過創建整體後排序和/或消除重複名單。

這樣做的最佳方法是什麼？坦率地說，我甚至不有線索如何正確地開始......

來源

2014-04-01 silmeth

在'itertools'將是你最好的選擇一些方法。 – sshashank124

我在看他們，但老實說，沒有發現任何真正有用的東西（至少直接解決了我的問題;-)）。我在考慮將所有的元組元素合併成一個長列表，然後從它們中取出所有組合，最終消除那些不包含每個元組中至少一個元素的元素。但我不確定這是最明智的方式。 – silmeth

你想在L中的項目powersets的笛卡爾積 - 除了當其中任何一個都是空的。一種方法是在我們構建powerset時只留下空的元素。

from itertools import product, combinations, chain 
L = [(1, 2, 3), (2, 4)] 
def powerset(iterable): 
    "powerset minus the empty element" 
    s = list(iterable) 
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1)) 

print [list(chain.from_iterable(c)) for c in product(*(powerset(x) for x in L))]

打印

[[1, 2], [1, 4], [1, 2, 4], [2, 2], [2, 4], [2, 2, 4], [3, 2], [3, 4], [3, 2, 4], [1, 2, 2], [1, 2, 4], [1, 2, 2, 4], [1, 3, 2], [1, 3, 4], [1, 3, 2, 4], [2, 3, 2], [2, 3, 4], [2, 3, 2, 4], [1, 2, 3, 2], [1, 2, 3, 4], [1, 2, 3, 2, 4]]

來源

2014-04-02 00:01:26

讓我們兩個列出了X和Y來表示，其長度由|X|和|Y|表示。

powerset(X)長度爲2^|X|，powerset（Y）的長度爲2^|Y|。

所以兩個電源的產品長度爲2^(|X|+|Y|)。對於本產品中的每個項目，我們都需要組合這些部件，然後採集（從部件中刪除重複部分）以形成一個新的集合。然後，我們需要將這個集合中的集合從集合中刪除。必須採用完整集合的集合可能需要大量內存，因爲它需要一次將完整集合保存在內存中。

但是，我認爲有一個更快的方法來達到預期的最終結果。如果您將X和Y組合成一組，XY，則XY的電力組長度爲2^(|XY|)。這個長度小於2^(|X|+|Y|)如果X和Y共享任何項目。因此，您爲每個共同項目節省了2倍。

對於這個powerset中的每個項目，我們只需要檢查X和Y中的一個元素。收集所有這些項目，我們就完成了。由於結果可以由迭代器生成，所以它的工作量少得多，而且佔用的內存也較少。

import itertools as IT 

def powerset(iterable, reverse=False, rvals=None): 
    """powerset([1,2,3]) -->() (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)""" 
    s = list(iterable) 
    N = len(s) 
    if rvals is None: 
     rvals = range(N, -1, -1) if reverse else range(N + 1) 
    return IT.chain.from_iterable(
     IT.combinations(s, r) for r in rvals) 

def powerreps(X, Y): 
    """ 
    Return powerset with at least one representative from X and Y 
    """ 
    XY = set(X).union(Y) 
    for rep in powerset(XY, rvals=range(2, len(XY))): 
     if any(x in rep for x in X) and any(y in rep for y in Y): 
      yield rep 

X, Y = (1, 2, 3), (2, 4) 
print(list(powerreps(X, Y)))

產生

[(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]

來源

2014-04-01 23:59:34 unutbu

列表中不同元組的元素的組合

回答

相關問題