Python: 不冗余的列表项之间的比较

Question

假设我有一个列表嵌套在字典的键中。所以像这样：

d = {'people':['John', 'Carry', 'Joe', 'Greg', 'Carl', 'Gene']}

我想比较列表中的人，这样我就可以制作一个连接首字母相同的名字的图表。

我想出了一个嵌套的 for 循环来尝试解决这个问题：

for subject in d.keys():
        for word1 in d[people]:
            for word2 in d[people]:
                if word1[0] == word2[0]:
                    g.connectThem(word1,word2)

但是嵌套的 for 循环可能会变得多余，因为它会重复进行两次相同的比较。有什么办法可以使比较没有冗余吗？

Answer 1

您可以使用 itertools.combinations

遍历对

for pair in itertools.combinations(d['people'], 2):
    first, second = pair
    if first[0] == second[0]:
        g.connectThem(first, second)

这些是从 combinations

中生成的对

[('John', 'Carry'), ('John', 'Joe'), ('John', 'Greg'), ('John', 'Carl'), ('John', 'Gene'),
 ('Carry', 'Joe'), ('Carry', 'Greg'), ('Carry', 'Carl'), ('Carry', 'Gene'),
 ('Joe', 'Greg'), ('Joe', 'Carl'), ('Joe', 'Gene'),
 ('Greg', 'Carl'), ('Greg', 'Gene'),
 ('Carl', 'Gene')]

注意你没有重复的问题（通过颠倒对的顺序）。
假设您的 connectThem 函数有效，这应该会产生您想要的行为。

Answer 2

如果你想将列表中的人相互比较，这样我就可以制作一个连接以相同首字母开头的名字的图表。然后使用字典并在 d["people"] 上进行一次传递，其中您使用名称的第一个字母作为键，因此解决方案是 0(n) 并且比二次得到所有组合的效率明显更高，后者会创建大部分不必要的配对：

d = {"people":['John', 'Carry', 'Joe', 'Greg', 'Carl', 'Gene']}

from collections import defaultdict

my_d = defaultdict(list)

for v in d["people"]:
    my_d[v[0]].append(v)
print(my_d)
defaultdict(<type 'list'>, {'C': ['Carry', 'Carl'], 'J': ['John', 'Joe'], 'G': ['Greg', 'Gene']})

您现在可以将具有共同名字的完整姓名列表传递给一种方法，只需迭代 my_d.

的值即可将其添加到图表中

如果您想在长度大于 2 的列表中创建人员组合，那么您可以使用原始列表来避免创建多个不必要的组合。它只会组合您想要的实际名称。

因此，要处理重复的名称，只对具有共同首字母的名称进行组合，并且只考虑具有链接的组，即具有非唯一首字母的名称：

from collections import defaultdict
# store all names in groups, grouped by common first letter in names
my_d = defaultdict(set)

for v in d["people"]:
     # 0(1) set lookup avoids adding names twice
    if v not in my_d[v[0]]:
        my_d[v[0]].add(v)


from itertools import combinations

for group in my_d.itervalues():
    # two elements are a combination
    if len(group) == 2:
        g.connectThem(group[0],group[1])   
    # ignore uniques names ?     
    elif len(group) > 2:
        for n1,n2  in combinations(group,2):            
            g.connectThem(n1 ,n2)

完全不使用 itertools 我们可以看到，因为我们的线性传递创建了一个分组字典，所以我们可以简单地遍历输出字典中的每个值列表并创建唯一配对：

for group in my_d.itervalues():
    for ind, n1 in enumerate(group):
        for n2 in group[ind+1:]:
            print(n1,n2)
('Carry', 'Carl')
('John', 'Joe')
('Greg', 'Gene')

Python: 不冗余的列表项之间的比较

Python: Comparison between list items that isn't redundant

python

for-loop

optimization

comparison

graph-algorithm