想象一下，我有一個帶有字串鍵和整數值的字典，例如：
{'255': 8,
'323': 1,
'438': 1,
'938': 2,
'166': 1,
'117': 10,
'777': 2
}
我想創建一個包含以下資訊的新字典：
- 鍵=一些新的唯一字串（可以是任何東西）
- values =上述字典中與任何匹配鍵中的任何字符匹配的上述字典中所有鍵的值的總和。
在上面的示例中，結果將類似于：
{
'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有一個 2 與 .in 中的 2 匹配323。然后 3's in323也匹配 3 in 438。最后，in438中的 8（或 3）匹配 中的 8（或 3）938。因此，以相同的順序添加這些鍵的值，我們得到 8 1 1 2 = 12。
上述鍵值 ( group1) 均未與其余鍵值（用于鍵166、117、777; 組成group2）合并，因為鍵中的任何字符都不group1匹配鍵中的任何字符group2。
166Group2 是通過將 1 from 匹配到 1s in117并將 7 in 匹配117到 7s in以相同的方式創建的777。
最后注意事項：
- 只有單個字符需要匹配鍵之間的至少一個其他單個字符才能包含在“組”中
- 我剛剛解釋上述值總和的順序無關緊要，結果應該從該組中的任何一對開始
- 關鍵字符將始終是數字
- 提醒一下，輸出字典的鍵可以是任何東西。為了方便起見，我使用了
group1和group2
什么是實作這一目標的有效方法？
我考慮將鍵值轉換為numpy矩陣，其中行表示單個鍵，串列示每個字符的值。但是，沿著這條路走下去很快就會變得相當復雜，如果有更好的方法，我寧愿避免它。
uj5u.com熱心網友回復：
您可以使用聯合查找資料結構來解決此問題。該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}
uj5u.com熱心網友回復：
嘗試：
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，值是原始字典中的值串列，它們與鍵共享一個字符。注意：串列在鍵之間共享- 這些串列的總數等于不同組的總數。
uj5u.com熱心網友回復：
這類似于@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}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/465133.html
下一篇：如何從字串中的常見元素創建字典