如何找到所有可能的组合与忽略的情况

Question

我目前正在试图找出如何找到所有可能的组合与某些忽略的案例附加到它。

我会尽我所能在这里解释。

dct = {
'1': "4 7 3",
'2': "6 3 4",
'3': "8 10 11",
'4': "11 9 3",
'5': "11 8 4",
'6': "1 3 11",
'7': "10 9 10",
'8': "11 8 6",
'9': "1 1 2",
'10': "11 6 8",
'11': "2 8 9" }

这个词中的值是键不能去的数字。因此，值4、7和3永远找不到键"1“，现在让我们说，键"1”将值2添加到其可能的组合键列表中。现在，键"1“不能有值6、3和4，因为它们不能与值2结合使用。

把它想象成一个巨大的、过于复杂的交叉口和交通灯。每个数字代表一组交通灯。如果让汽车前进的一组特定信号灯被激活，任何使汽车转向同一条道路并极有可能造成影响的交通灯都将被停用。

在过去的三个多小时里，我一直在努力弄清楚我的头发，任何帮助都是非常感谢的！

Answer 1

可以使用以下递归生成器生成所有长度的所有可能组合。如果您想要最大可能的长度，您可以计算max(..., key=len)。

from typing import Set


dct = {int(k): {int(x) for x in v.split()} for k, v in dct.items()}


def combinations(nodes: Set[int], banned: Set[int]):
    candidates = dct.keys() - nodes - banned
    candidates = {
        c for c in candidates
        if not nodes.intersection(dct[c])
    }
    if not candidates:
        yield nodes
    else:
        candidates = {  # eliminate duplicates
            c for c in candidates
            if not nodes or c > max(nodes)
        }
        for c in candidates:
            yield from combinations(nodes | {c}, banned | dct[c])


from pprint import pprint

pprint(list(combinations(set(), set())))

产出如下：

[{8, 1, 2},
 {1, 2, 10, 5},
 {1, 11},
 {2, 5, 7},
 {8, 2, 7},
 {9, 3, 5},
 {3, 5, 7},
 {10, 4},
 {4, 6, 7},
 {8, 4, 7},
 {9, 10, 5},
 {9, 5, 6},
 {5, 6, 7},
 {11, 7},
 {8, 9}]

要计算最长的可能组合(可能不是唯一的)：

pprint(max(combinations(set(), set()), key=len))