我正在尝试为以下问题找到有效的解决方案:
我有一个字典列表，每个字典都具有与另一个字典相同的一组键。关联值在字典之间可以是相等的。我试图找到最小数量的键及其关联值，这将使每个字典都是唯一的。
例如，对于包含三个字典的列表:
list = [a, b, c]
where
a = {"key1": "alpha", "key2": "beta", "key3": "gamma"}
b = {"key1": "alpha", "key2": "beta", "key3": "eta"}
c = {"key1": "alpha", "key2": "zeta", "key3": "eta"}
所有三个字典的 key1 都有相同的值，因此可以删除该键，因为它的包含并不能确定字典的唯一性。另一方面，key2 和 key3 必须都包含在内，因为它们的集合使各自的字典唯一。
a = {"key2": "beta", "key3": "gamma"}
b = {"key2": "beta", "key3": "eta"}
c = {"key2": "zeta", "key3": "eta"}
我假设我循环遍历字典列表，因此可以在迭代中使用例如 collections.Counter 。 列表中字典的数量与键的数量一起是一个变量。我想以尽可能少的数量迭代列表(例如，在更新一个或多个计数器时一次？)。我相当确定有一个适合这个问题的算法，但无法用我的搜索关键字找到它。
编辑:每个最终字典必须具有与其他字典相同的键。因此，为每个单独的字典保留一组不同的键并不是一种选择。
最佳答案
精确的解决方案是 NP 困难的，但为了获得合适的近似值，您可以尝试使用 ID3 算法的变体来创建决策树:https://en.wikipedia.org/wiki/ID3_algorithm
您的情况的不同之处在于您必须在所有分支中选择相同的属性，因此它的工作方式如下:
- 从一组所有词典开始
- 对于每个属性，计算所有集合中其值的熵总和。 公式位于链接的文章中。
- 根据所选属性对集合进行分区，并丢弃所有仅包含一个字典的集合
- 如果仍有集合需要分区，则返回(2)
关于python - 找到使每个字典在多个字典中唯一的键的最小数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59422527/