python - 找到使每个字典在多个字典中唯一的最少键数

我正在尝试为以下问题找到有效的解决方案:我有一个字典列表，每个字典都与另一个字典具有相同的键集。关联值可以是相等的字典间。我试图找到 最小键数 及其关联值，这将使 每个 字典都是唯一的。例如对于由三个字典组成的列表:list = [a, b, c]wherea = {"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。 列表中的字典数量与键的数量一起是一个变量。 我想尽可能少地遍历列表(例如，在更新一个或多个计数器时一次？)。我相当确定这个问题有一个合适的算法，但我的搜索关键字找不到它。编辑:每个最终的 dict 必须与其他的具有相同的键。因此，为每个单独的 dict 保留一组不同的键不是一种选择。 最佳答案 我很高兴其他答案证实了我的怀疑，这是一个 NP 完全问题。目前没有已知的绕过方法，在最坏的情况下，尝试每个可能的 key 子集。这是我的算法，它在 O(n^2*2^k) 时间和 O(nk^2+2^k) 空间中运行，其中 n 是列表中的项目数，而 k 是每个项目的属性数。只要 2^k n^2 ，这就会在大致多项式时间内运行。 def get_unique_key_values(objs): key = get_unique_key(objs) return [{ k: obj[k] for k in key } for obj in objs ]def get_unique_key(objs): return get_unique_key_set(objs, { k for obj in objs for k in obj }, [])def get_unique_key_set(objs, keys, tested_keys): if len(keys) == 0 or not all_unique(objs): # keys is either the empty set, or this subset of keys # does not guarantee uniqueness return False # the smallest number of keys required for a unique key best_key_set = set(keys) # delete each key one at a time and check if the list of # items are still unique for del_key in keys: tmp_keys = set(keys) tmp_keys.remove(del_key) # if we've already tested this subset, skip it and all its children if tmp_keys in tested_keys: continue # keep track of subsets we've tested so we don't retest them--significant trimming tested_keys.append(tmp_keys) # generate a list of objects with only the current set of keys tmp_objs = [{ k: obj[k] for k in tmp_keys } for obj in objs] # continue to delete keys from the current subset until we find a subset # of size 1, or the current tmp_keys is optimal tmp_key_set = get_unique_key_set(tmp_objs, tmp_keys, tested_keys) if tmp_key_set == False: continue if len(tmp_key_set) < len(best_key_set): best_key_set = tmp_key_set return best_key_set# O(n^2) algorithm for checking that every element in the list is uniquedef all_unique(objs): for i in range(len(objs) - 1): for j in range(i + 1, len(objs)): if objs[i] == objs[j]: return False return Trueobjects = [ { 'a': 1, 'b': 2, 'c': 2 }, { 'a': 1, 'b': 3, 'c': 2 }, { 'a': 1, 'b': 3, 'c': 3 }]print(get_unique_key(objects))# prints set([ 'b', 'c' ])objects = [ { 'a': 1, 'b': 2, 'c': 2 }, { 'a': 2, 'b': 3, 'c': 2 }, { 'a': 3, 'b': 3, 'c': 3 }]print(get_unique_key(objects))# prints set([ 'a' ])我在编写此脚本时做了一些假设，例如所有对象都具有相同的属性集。如果某些属性仅存在于某些对象上，则您可能需要对脚本进行一些更改。您可以通过将 tested_keys 更改为集合并为键数组创建散列函数，将散列存储在集合中来加快速度。为对象字典创建哈希函数可以将 all_unique 转换为 O(n) 算法，从而减少 O(n2^k) 的总运行时间。具有讽刺意味的是，虽然显着减少了运行时间，但它增加了它成为指数时间算法的可能性，因为 2^k < n 更难满足。有关如何创建这些哈希的信息，请参阅 this answer。关于python - 找到使每个字典在多个字典中唯一的最少键数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59422527/