Return keys when solving Set Cover problem with a dictionary and the greedy 算法

Question

我有一个布景封面问题需要解决，我希望将布景名称返回给我。我认为存储命名集的一个好方法是在字典中。我发现这个 blog 实现了该算法但使用了集合列表，我正在尝试修改代码以容纳字典。

def set_cover2(universe, subsets):
    """Find a family of subsets that covers the universal set"""
    elements = set(e for s in subsets for e in subsets[s])
    # Check the subsets cover the universe
    if elements != universe:
        return None
    covered = set()
    cover = []
    # Greedily add the subsets with the most uncovered points
    while covered != elements:
        subset = max(subsets.values(), key=lambda s: len(s - covered))
        cover.append(subset)
        covered |= subset

    return cover

这个returns集合为列表：

universe = set(range(1, 11))
subsets = {"s1":set([1, 2, 3, 8, 9, 10]),
           "s2":set([1, 2, 3, 4, 5]),
           "s3":set([4, 5, 7]),
           "s4":set([5, 6, 7]),
           "s5":set([6, 7, 8, 9, 10])}


cover = set_cover2(universe, subsets)
print(cover)

即

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

但不是名字。

为了获取名称，我不能使用集合的值来识别名称，因为在我的实际数据中，一些子集可能是相同的（我想在那种情况下两者都可以）。不管怎样，我想要一个 returns 选择每个集合的名称的解决方案。

我想这一定可以通过修改 subset = max(subsets.values(), key=lambda s: len(s - covered)) 行来实现，但我不确定如何在保留算法集的同时获取从此操作中选择的集的名称。我该怎么做？

期望的输出：

["s1", "s3", "s4"]

Answer 1

查看评论：

def set_cover2(universe, subsets):
    """Find a family of subsets that covers the universal set"""
    # cosmetic change: same thing, just looks a bit nicer
    elements = set().union(*subsets.values())

    # ... some code here ...
  
    while covered != elements:
        # Use keys, account for this in the key function
        subset = max(subsets.keys(), key=lambda s: len(subsets[s] - covered))
        cover.append(subset)
        # since subset is a key now, change here as well
        covered |= subsets[subset]

    return cover

Return keys when solving Set Cover problem with a dictionary and the greedy 算法

Return keys when solving Set Cover problem with a dictionary and the greedy algorithm

python

dictionary

set

set-cover