algorithm - 将项目分组为子集(幂集)

Question

假设我有以下内容:

john: [a, b, c, d]
bob:  [a, c, d, e]
mary: [a, b, e, f]

或者稍微重新格式化以便您可以轻松查看分组:

john: [a, b, c, d]
bob:  [a,    c, d, e]
mary: [a, b,       e, f]

生成以下分组的最常见或最有效的算法是什么？

[john, bob, mary]: [a]
[john, mary]:      [b]
[john, bob]:       [c,d]
[bob, mary]:       [e]
[mary]:            [f]
[john]:            []
[bob]:             []

快速谷歌搜索后，上面的键似乎代表“电源组”。所以我计划以下实现:

1) 生成幂集 {{j, b, m}, {j, m}, {j, b} {b, m}, {m}, {j}, {b}}//j =约翰，b = 鲍勃，m = 玛丽

2) 生成所有字母的集合:{a, b, c, d, e, f}

3) 遍历子集，对于每个字母，查看字母是否存在于子集的所有元素中

所以...

subset = {j, b, m}

letter = a
    j contains a? true
    b contains a? true
    m contains a? true
        * add a to subset {j, b, m}

letter = b
    j contains b? true
    b contains b? false, continue

letter = c
    j contains c? true
    b contains c? true
    m contains c? false, continue
.....

subset = {j, m}
.....

有没有更好的解决方案？

编辑:上述算法存在缺陷。例如，{j, m} 也会包含我不想要的“a”。我想我可以简单地修改它，以便在每次迭代中，我也检查这个字母是否“不在”不在这个集合中的元素。所以在这种情况下，我还会检查:

if b does not contain a

Answer 1

您可以使用两本 map /字典来实现这一点，其中一个是另一个的“逆向”。对于第一张 map ，“键”是名称，“值”是字符列表。第二张 map 将字母作为键，将与其关联的名称列表作为值。

在 Python 中

nameDict = {'john' : ['a', 'b', 'c', 'd'], 'bob' : ['a', 'c', 'd', 'e'], 'mary' : ['a', 'b', 'e', 'f']}

reverseDict = {}
for key,values in nameDict.items():
    for v in values:
        if v in reverseDict.keys():
            reverseDict[v].append(key)
        else:
            reverseDict[v] = [key] # If adding v to dictionary for the first time it needs to be as a list element

# Aggregation
finalDict = {}
for key,values in reverseDict.items():
    v = frozenset(values)
    if v in finalDict.keys():
        finalDict[v].append(key)
    else:
        finalDict[v] = [key] 

这里，reverseDict 包含了你想要的映射 a -> [john, bob, mary], b -> [john, mary] 等。你也可以检查 if john 不包含 a通过检查 reverseDict['a'] 返回的列表是否包含 john。

[编辑] 将聚合添加到 finalDict。

您可以使用 frozensets 作为字典键，因此 finalDict 现在包含正确的结果。打印字典:

frozenset({'bob', 'mary'})
['e']

frozenset({'mary'})
['f']

frozenset({'john', 'bob'})
['c', 'd']

frozenset({'john', 'mary'})
['b']

frozenset({'john', 'bob', 'mary'})
['a']