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

Question

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

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

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

对于这个例子，当开始生成组合时，我需要添加(1,2)then(2,3)但我不能添加(2,4)，因为 number2已经使用了 2 次，[(1,2),(2,3)]所以我需要跳过或删除这些项目（包含数字 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)]等等。

有人可以帮我怎么做吗？

标签： python

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