python - 使用递归生成组合并跳过或删除项目

Question

我在 python 中有这样的元组数组:

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

我需要生成给定长度的所有组合，但有一些条件。元组中应该始终只有 2 个相同的数字。

对于这个例子，当开始生成组合时，我需要添加 (1,2) 然后 (2,3) 但是我不能添加 ( 2,4)，因为数字2已经在[(1,2),(2,3)]中使用了2次所以我需要跳过或删除起始数组这些项目(其中包含数字 2):(2,4),(2,5),(2,6),(3,2) 并继续生成。给定长度 3 的第一个组合将是 [(1,2),(2,3),(3,1)]，第二个 [(1,2),(2,3 ),(3,4)] 然后是 [(1,2),(2,4),(3,1)] 等等。

有人可以帮我怎么做吗？

Answer 1

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

from collections import Counter
def groups(d, l, c = []):
  if l == len(c):
    yield c
  else:
    for i in d:
      if i not in c:
        _c = Counter([j for k in [*c, i] for j in k])
        if all(j < 3 for j in _c.values()):
           yield from groups(d, l, c+[i])

data = [(1,2),(2,3),(2,4),(2,5),(2,6),(3,1),(3,2),(3,4)]
result = list(groups(data, 3))
final_result = [a for i, a in enumerate(result) if all(any(c not in h for c in a) for h in result[:i])]

输出:

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