元组列表的唯一组合

Question

给定一个三元组列表，例如：[(1,2,3), (4,5,6), (7,8,9)]如何计算所有可能的组合和子集组合？

在这种情况下，结果应如下所示：

[
(1), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,4,7), (1,4,8), (1,4,9), (1,5,7), (1,5,8), (1,5,9), (1,6,7), (1,6,8), (1,6,9),
(2), ...,
(3), ...,
(4), (4,7), (4,8), (4,9), 
(5), (5,7), (5,8), (5,9), 
(6), (6,7), (6,8), (6,9), 
(7), (8), (9)
]

• 具有相同元素的所有元组都被视为相同
• 从相同的元组推导出的组合是不允许（例如这些不应该是在溶液中：(1,2)，(4,6)或(7,8,9)）

Answer 1

您可以将递归与生成器一起使用：

data = [(1,2,3), (4,5,6), (7,8,9)]
def combos(d, c = []):
   if len(c) == len(d):
     yield c
   else:
     for i in d:
        if i not in c:
           yield from combos(d, c+[i])

def product(d, c = []):
  if c:
    yield tuple(c)
  if d:
    for i in d[0]:
      yield from product(d[1:], c+[i])

result = sorted({i for b in combos(data) for i in product(b)})
final_result = [a for i, a in enumerate(result) if all(len(c) != len(a) or len(set(c)&set(a)) != len(a) for c in result[:i])]

输出：

[(1,), (1, 4), (1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 5), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 6), (1, 6, 7), (1, 6, 8), (1, 6, 9), (1, 7), (1, 8), (1, 9), (2,), (2, 4), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 5), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 6), (2, 6, 7), (2, 6, 8), (2, 6, 9), (2, 7), (2, 8), (2, 9), (3,), (3, 4), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 5), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 6), (3, 6, 7), (3, 6, 8), (3, 6, 9), (3, 7), (3, 8), (3, 9), (4,), (4, 7), (4, 8), (4, 9), (5,), (5, 7), (5, 8), (5, 9), (6,), (6, 7), (6, 8), (6, 9), (7,), (8,), (9,)]

Answer 2

这是带有简单for循环的非递归解决方案。通过应用于set输出的元组列表来强制唯一性。

lsts = [(1,2,3), (4,5,6), (7,8,9)]

res = [[]]
for lst in lsts:
    res += [(*r, x) for r in res for x in lst]

# print({tuple(lst) for lst in res[1:]})
# {(5, 9), (4, 7), (6, 9), (1, 4, 7), (2, 6, 9), (4, 8), (3, 4, 7), (2,
# 8), (2, 6, 8), (9,), (2, 5, 8), (1, 6), (3, 6, 8), (2, 5, 9), (3, 5,
# 9), (3, 7), (2, 5), (3, 6, 9), (5, 8), (1, 6, 8), (3, 5, 8), (2, 6,
# 7), (4, 9), (6, 7), (1,), (2, 9), (1, 6, 9), (3,), (1, 5), (5,), (3,
# 6), (7,), (3, 6, 7), (1, 5, 9), (2, 6), (2, 4, 7), (1, 5, 8), (3, 4,
# 8), (8,), (3, 4, 9), (1, 4), (1, 6, 7), (3, 9), (1, 9), (2, 5, 7), (3,
# 5), (2, 7), (2, 4, 9), (6, 8), (1, 5, 7), (2,), (2, 4, 8), (5, 7), (1,
# 4, 8), (3, 5, 7), (4,), (3, 8), (1, 8), (1, 4, 9), (6,), (1, 7), (3,
# 4), (2, 4)}