获取“无冲突”列表的所有详尽组合

Question

假设我有一个类似于以下列表的列表：

lists = [[1,2], [3,4], [4,5], [6,7]]

让我们定义，如果两个列表不共享任何一个元素，那么它们“没有冲突”。因此，在上面的示例中，只有[3,4]和[4,5]是冲突的。我已经可以通过使用以下命令来检查两个列表是否存在冲突：

from itertools import combinations

for sets in combinations(lists, 2):
    if not set(sets[0]).isdisjoint(set(sets[1])):
        print(f'the set {sets} has a conflict!')

现在，我需要得到列表集合的所有可能的、彼此不冲突的详尽组合。因此，对于上面的示例，组合将是[[1,2], [6,7], [3,4]]和[[1,2], [6,7], [4,5]]。无论我有多少组冲突的列表，你如何建议找到这样的组合？

Answer 1

这是另一种使用动态编程的方法：

lists = [[1,2], [3,4], [4,5], [6,7]]
tups = [tuple(lst) for lst in lists]#tuples needed for set operations

def validate_combo(list_of_lists):
    '''helper function to validate a combo'''
    flattened = [num for lst in list_of_lists for num in lst]
    return len(flattened) == len(set(flattened))

DP = [[item] for item in tups] #dynamic programming table
for i in range(len(tups)):
    for j in range(len(tups)):
        temp = list(DP[i])
        temp.append(lists[j])
        if validate_combo(temp):
            DP[i].append(tups[j])
            
#elimiate duplicates
result = []
for lst in DP:
    if set(lst) not in result:
        result.append(set(lst))

print(result)

#[{(6, 7), (1, 2), (3, 4)}, {(6, 7), (4, 5), (1, 2)}]

Answer 2

您可以对生成器使用递归：

def combos(d, c = []):
   if c and sum(map(len, c)) == len({i for b in c for i in b}):
      yield sorted(c)
   for i in d:
      yield from combos(d[1:], c+[i])
   
def get_results(d):
   k = sorted(combos(d), key=len)
   return [a for i, a in enumerate(k) if all(not all(l in j for l in a) for j in k[i+1:])]

for i in [[[1,2], [3,4], [4,5], [6,7]], [[1,2], [3,4], [4,5], [5,6]]]:
   print(get_results(i))

输出：

[[[1, 2], [3, 4], [6, 7]], [[1, 2], [4, 5], [6, 7]]]
[[[1, 2], [4, 5]], [[1, 2], [3, 4], [5, 6]]]