在python中插入图形时处理索引

Question

考虑以下列表：

["abc", "abx", "axx", "abx", "abc"]

现在把列表中的每个元素都看作一个图的顶点。如果两个元素只有一个字符不同，那么两个顶点是相连的：

abc > abx
abc > abx

等等。最后的结果是：

{"0":["1","3"],"1":["0","2","4"],"2":["1","3"],"3":["0","3","4"],"4":["1","3"]}

数字是索引。我已经做了一个函数来检查
顶点应该是连接的（它返回布尔值），但主要的问题是当列表中有多个元素时（在我的示例中是两个“abc”和两个“abx”）。问题是当我想找到和元素的索引时，比如“abc”。Python会自动返回较小的索引（即0），但是当将“abx”与“abc”这两个指数（0和3）都很重要，因为有C（5，2）=10对需要检查，所以变得很糟糕。 我想我应该告诉python检查每个元素是否不止一个，并记住它使用了多少次，我真的不知道如何进一步开发这个想法（也不知道它是否有用）以及如何在代码中执行它。 谢谢你的关注

Answer 1

您可以执行以下操作：

from itertools import combinations as comb
from collections import defaultdict

# a,b are strings from the list, i,j are their respective indexes
edges = [(i,j) for (i,a),(j,b) in comb(enumerate(lst), 2) if len(set(a)-set(b))==1]
# [(0, 1), (0, 3), (1, 2), (1, 4), (2, 3), (3, 4)]

dd = defaultdict(list)
for i, j in edges:
    dd[i].append(j)
    dd[j].append(i)
# {0: [1, 3], 1: [0, 2, 4], 2: [1, 3], 3: [0, 2, 4], 4: [1, 3]}

它使用^{}获取索引，^{}获取所有可能的索引对Set difference在conditional comprehension中被用来过滤掉所有在1个字母和一个^{}中不同的配对，以便从这些边构建最终的数据结构