如何找到忽略大小写的所有可能组合

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" }

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

把它想象成一个巨大的、带有红绿灯的复杂十字路口。其中每个数字代表一组交通灯。如果要激活一组让汽车先行的特定信号灯，则任何使汽车转向同一条道路并且很可能造成碰撞的交通信号灯都将保持停用状态。

在过去的 3 个小时左右的时间里，我一直在绞尽脑汁试图解决这个问题，我们将不胜感激任何帮助！

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

如何找到忽略大小写的所有可能组合

How to find all possible combinations with ignore cases

python

combinations

dictionary