嵌套循环避免自我比较和相互比较

Question

因为这一定是很常见的情况，所以我想知道是否有任何预先存在的解决方案。

假设我有一组 N 个字符串，我正在计算它们之间的距离。在这种情况下，它是一个汉明距离，但这并不重要。

如果我想尽快完成，我会避免这样的自我比较：

 def hamming_distance(string1, string2):
     """Return the Hamming distance between equal-length sequences"""
     if len(string1) != len(string2):
         raise ValueError("Undefined for sequences of unequal length")
     return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))


ratios=[]
 for a, i in enumerate(string_list):
     for b, j in enumerate(string_list):
         if a == b: # Avoid self comparisons for speed
             break
     ratios.append(hamming_distance(string_list[i], string_list[j]))
 return ratios

但由于这是 'symmetric'，我也可以放弃任何相互比较，如果字符串很多 and/or 大，这会提高速度。

在上面的设置中是否有一种通用的 accepted/elegant 方法？

我也知道，通常建议避免嵌套循环，因为它们可能很慢 - 所以如果有更好的方法来实现列表上的这种成对迭代（也许是 collections 中的东西？）并结合避免自我比较和相互比较，我洗耳恭听。

Answer 1

可以在外循环中限制嵌套for从下一项开始到当前项。这样，您只需运行通过每个唯一一次：

for i, s1 in enumerate(string_list):
   for s2 in string_list[i+1:]:
      ratios.append(hamming_distance(s1, s2))
return ratios

你可以把它放在一个列表中：

ratios = [(s1, s2, hamming_distance(s1, s2)) for i, s1 in enumerate(string_list) 
                                                     for s2 in string_list[i+1:]]

您可以将字符串作为结果的一部分放入元组中，就像我在列表 comp 中所做的那样。

Answer 2

你要找的是itertools.combinations()实现的。

>>> import itertools
>>> a = [1,2,3]
>>> list(itertools.combinations(a, 2))
[(1, 2), (1, 3), (2, 3)]

所以在你的情况下它看起来像：

for a, b in itertools.combinations(string_list, 2):
    ratios.append(hamming_distance(a, b))

嵌套循环避免自我比较和相互比较

nested loops avoiding self and reciprocal comparisons

python

nested-loops

hamming-distance