0

我有一个套装封面问题要解决我希望将套装名称返回给我的地方。我认为存储命名集的好方法是在字典中。我发现这个实现算法但使用集合列表的博客，我正在尝试修改代码以适应字典。

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

这将集合作为列表返回：

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)

IE

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

但不是名字。

为了获得名称，我不能使用集合的值来识别名称，因为在我的实际数据中，一些子集可能是相同的（我猜在这种情况下两者都可以）。无论如何，我想要一个返回每个选定集合名称的解决方案。

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

期望的输出：

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

1 回答 1

0

看评论：

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
于 2020-11-16T18:44:10.177 回答