如果关键字字符串中的任何字符匹配，则求和字典的值

Question

想象一下，我有一个包含字符串键和整数值的字典，比如：

{'255': 8,
'323': 1,
'438': 1,
'938': 2,
'166': 1,
'117': 10,
'777': 2
}

我想创建一个包含以下信息的新词典：

• keys=一些新的唯一字符串(可以是任何字符串)
• values=上述字典中与任何匹配关键字中的任何字符匹配的所有关键字的值的sum

在上面的例子中，结果看起来像：

{
'group1' : 12, # Sum of key values for '255' (8), '323' (1), '438' (1), '938' (2)
'group2' : 13  # Sum of key values for '166' (1), '117' (10), '777' (2)
}

为了澄清，group1是以以下方式创建的：255有一个与323中的2匹配的2。则323中的3也与438中的3相匹配。最后，438中的8(或3)与938中的8或3相匹配。因此，将这些键的值按相同的顺序相加，我们得到8+1+1+2=12。

上述键值(group1)均未与其余键值(对于键166、117、777；组成group2)合并，因为group1键中的字符均未与group2键中的任何字符相匹配。

通过将166中的1与117中的1相匹配以及将117中的7与777中的7相匹配，以相同的方式创建Group2。

最后注释：

• 只有一个字符需要与要包含在"中的键之间的至少一个其他单个字符相匹配；组">
• 我刚才解释的上述值总和的顺序应该无关紧要，结果应该从该组中的任何一对开始
• 关键字符将始终是数字
• 提醒您，输出字典的键可以是任何东西。为了方便，我使用了group1和group2

实现这一目标的有效方法是什么

我考虑将键值转换为numpy矩阵，其中行表示单个键，列表示每个字符的值。然而，走这条路很快就会变得相当复杂，如果有更好的方法，我宁愿避免它。

Answer 1

您可以使用并集查找数据结构来解决此问题。networkx包提供了一个实现，但没有什么可以阻止您编写自己的实现。

本质上，我们维护了一个不相交集合的集合。最初，每个字符串都属于自己的不相交集。对于每一对字符串，如果它们有共同的字母，我们就将它们所属的不相交集合并集。这最终给了我们要寻找的组。

从这里，我们使用.to_sets()方法来获得分组，并计算所需的和：

from networkx.utils.union_find import UnionFind
data = # dictionary in question, omitted for brevity
keys = list(data.keys())
uf = UnionFind(data.keys())
for outer_idx in range(len(keys)):
for inner_idx in range(outer_idx + 1, len(keys)):
if set(keys[outer_idx]) & set(keys[inner_idx]):
uf.union(keys[outer_idx], keys[inner_idx])
result = {}
for idx, group in enumerate(uf.to_sets()):
result[idx] = sum(data[key] for key in group)
print(result)

该输出：

{0: 12, 1: 13}

Answer 2

尝试：

d = {"255": 8, "323": 1, "438": 1, "938": 2, "166": 1, "117": 10, "777": 2}
keys, groups = list(d), {}
while keys:
current = keys.pop()
s_current = set(current)
for k in groups:
if s_current.intersection(k):
groups[k].append(d[current])
groups[current] = groups[k]
break
else:
groups[current] = [d[current]]
out = {}
for k, v in groups.items():
if id(v) not in out:
out[id(v)] = sum(v)

print(out)

打印：

{140318922050368: 13, 140318911221184: 12}

---

一点解释：

我们创建了一个临时字典groups，其中键来自原始字典d，值是原始字典中与键共享一个字符的值的列表。注意：这些列表是键之间共享的-这些列表的总数等于不同组的总数。

Answer 3

这与@BrokenBenchmark的答案类似，但它是自包含的，而且它还按数字优先对事物进行分组，因此在所有字符串上都没有O(n^2)双嵌套循环。

from collections import defaultdict
def get_edges(strings):
# group together common digits.
by_digit = [[] for _ in range(10)]
for i, s in enumerate(strings):
for digit in map(int, s):
by_digit[digit].append(i)
# attach the first of each group to the rest.
for digit_locations in by_digit:
if digit_locations:
x = digit_locations[0]
for y in digit_locations[1:]:
yield (x, y)
def union_find_groups(edges, n):
parent = list(range(n))
size = [1] * n
def find(x):
# find (path-splitting)
while parent[x] != x:
x, parent[x] = parent[x], parent[parent[x]]
return x
def union(x, y):
x = find(x)
y = find(y)
if x == y:
return
# Union (by size)
if size[x] < size[y]:
x, y = y, x
parent[y] = x
size[x] += size[y]
for x, y in edges:
union(x, y)

result = defaultdict(list)
for x in range(n):
result[find(x)].append(x)
return result.values()
def main(input_data):
strings = list(input_data.keys())
index_groups = union_find_groups(get_edges(strings), len(strings))
string_groups = [[strings[i] for i in group] for group in index_groups]
print(string_groups)
results = [sum(input_data[s] for s in group) for group in string_groups]
return {f"group{i}": total for i, total in enumerate(results)}
if __name__ == "__main__":
result = main({
'255': 8,
'323': 1,
'438': 1,
'938': 2,
'166': 1,
'117': 10,
'777': 2
})
print(result)

结果：

[['255', '323', '438', '938'], ['166', '117', '777']]
{'group0': 12, 'group1': 13}