让我们考虑距离d(a, b) = number of digits which are pairwise different in a and b，例如：
d(1003000000, 1000090000) = 2 # the 4th and 6th digits don't match
（（我们仅使用10位数字）和此列表：
L = [2678888873,
2678878873, # distance 1 from L[0]
1000000000,
1000040000, # distance 1 from L[2]
1000300000, # distance 1 from L[2], distance 2 from L[3]
1000300009, # distance 1 from L[4], distance 2 from L[2]
]
我想找到最小数量的点P，以使列表中的每个整数与P中点的距离<= 1。
我认为这里的数字是3：列表中的每个数字都位于距离<= 1，即2678888873、1000000000或1000300009。
我想通过首先计算距离矩阵即M[i, j] = d(L[i], L[j])，可以实现O（n ^ 2）算法。
还有更好的方法，尤其是使用Numpy吗？（也许Numpy / Scipy中有内置算法？）
PS：如果我们将这些10位整数视为字符串，我们接近在具有Levenshtein距离的许多单词的列表中找到最小数目的簇。
PS2：我知道该距离在字符串上有一个名称：Hamming distance。
让我们了解一下距离度量标准。给定数字P（不一定在L中），如果L的两个成员在P的距离1之内，则它们各自与P共享9个数字，但不一定是相同的，因此它们只能保证彼此共享8位数字。因此，任何两个具有距离2的数字都被保证为两个唯一的P，它们彼此之间的距离为1（以及彼此之间的距离为2）。您可以使用此信息来减少优化P所需的蛮力工作。
假设您有一个距离矩阵。您可以立即丢弃条目少于3的行（或列），它们将自动成为它们自己的群集。对于等于2的其余条目，构造一个可能的P值列表。查找L的每个元素中的1个以内的P的元素数（另一个距离矩阵）。按邻居数对P排序，然后选择。您将需要在每次迭代时更新矩阵，因为要删除具有最大邻域的成员，以避免由于重叠而导致效率低下的分组（L的成员与P的多个成员接近）。
您可以先将其转换为2D数字数组，然后以numpy的形式计算L的距离矩阵：
L = np.array([2678888873, 2678878873, 1000000000, 1000040000, 1000300000, 1000300009])
z = 10 # Number of digits
n = len(L) # Number of numbers
dec = 10**np.arange(z).reshape(-1, 1).astype(np.int64)
digits = (L // dec) % 10
digits现在是一个10xN数组：
array([[3, 3, 0, 0, 0, 9],
[7, 7, 0, 0, 0, 0],
[8, 8, 0, 0, 0, 0],
[8, 8, 0, 0, 0, 0],
[8, 7, 0, 4, 0, 0],
[8, 8, 0, 0, 3, 3],
[8, 8, 0, 0, 0, 0],
[7, 7, 0, 0, 0, 0],
[6, 6, 0, 0, 0, 0],
[2, 2, 1, 1, 1, 1]], dtype=int64)
您可以使用digits和digits沿右轴计算!=与它本身或sum与任何其他10xM阵列之间的距离：
distance = (digits[:, None, :] != digits[..., None]).sum(axis=0)
结果：
array([[ 0, 1, 10, 10, 10, 10],
[ 1, 0, 10, 10, 10, 10],
[10, 10, 0, 1, 1, 2],
[10, 10, 1, 0, 2, 3],
[10, 10, 1, 2, 0, 1],
[10, 10, 2, 3, 1, 0]])
我们只关心该矩阵的上三角（或下三角），因此我们可以立即掩盖另一个三角：
distance[np.tril_indices(n)] = z + 1
查找P的所有候选值：L的所有元素，以及具有距离2的元素之间的所有对：
# Find indices of pairs that differ by 2
indices = np.nonzero(distance == 2)
# Extract those numbers as 10xKx2 array
d = digits[:, np.stack(indices, axis=1)]
# Compute where the difference is nonzero (Kx2)
locs = np.diff(d, axis=2).astype(bool).squeeze()
# Find the index of the first digit to replace (K)
s = np.argmax(locs, axis=0)
P的额外值是从d的每一半构成的，用k表示的数字替换为另一半：
P0 = digits[:, indices[0]]
P1 = digits[:, indices[1]]
k = np.arange(s.size)
tmp = P0[s, k]
P0[s, k] = P1[s, k]
P1[s, k] = tmp
Pextra = np.unique(np.concatenate((P0, P1), axis=1)
所以现在您可以计算P的总可能性：
P = np.concatenate((digits, Pextra), axis=1)
distance2 = (P[:, None, :] != digits[..., None]).sum(axis=0)
您可以根据距离丢弃Pextra中与digits元素匹配的任何元素：
mask = np.concatenate((np.ones(n, bool), distance2[:, n:].all(axis=0)))
P = P[:, mask]
distance2 = distance2[:, mask]
现在您可以将P与L进行迭代距离，并选择P的最佳值，然后从距离矩阵中删除所有已选择的值。从P进行的贪婪选择不一定是最佳的，因为由于重叠，替代组合可能需要较少的元素，但是这对于简单（但有些昂贵）的图遍历算法来说是一个问题。以下代码段仅显示了一个简单的贪婪选择，对于您的玩具示例来说，它会很好地工作：
distMask = distance2 <= 1
quality = distMask.sum(axis=0)
clusters = []
accounted = 0
while accounted < n:
# Get the cluster location
best = np.argmax(quality)
# Get the cluster number
clusters.append(P[:, best].dot(dec).item())
# Remove numbers in cluser from consideration
accounted += quality[best]
quality -= distMask[distMask[:, best], :].sum(axis=0)
最后几步可以使用集合和图形进行优化，但这显示了一种有效方法的起点。对于大数据，这将变慢，但可能并非如此。做一些基准测试来决定要花多少时间进行优化而不是仅仅运行算法。