在不使用嵌套循环的情况下查找列表中所有对的有效方法

Question

假设我有一个存储许多二维点的列表。在这个列表中，一些位置存储了相同的点，将存储相同点的位置的索引视为索引对。我想找到列表中的所有对和 return 所有 2 x 2 索引对。列表中可能有一些点重复了两次以上，但只需要将第一个匹配视为一对。

例如，在下面的列表中，我总共有9个点，其中有5个位置包含重复点。索引0、3、7存储相同的点（[1, 1]），索引1和6存储相同的点（[2, 3]）。

[[1, 1], [2, 3], [1, 4], [1, 1], [10, 3], [5, 2], [2, 3], [1, 1], [3, 4]]

因此，对于此列表，我想 return 索引对作为（索引 0，索引 3）和（索引 1，索引 6）。我能想出的唯一解决方案是通过嵌套循环来实现，我将其编码如下

A = np.array([[1, 1], [2, 3], [1, 4], [1, 1], [10, 3], [5, 2], [2, 3], [1, 1], [3, 4]], dtype=int)

# I don't want to modified the original list, looping through a index list insted.
Index = np.arange(0, A.shape[0], 1, dtype=int) 
Pair = [] # for store the index pair
while Index.size != 0:

    current_index = Index[0]
    pi = A[current_index]
    Index = np.delete(Index, 0, 0)

    for j in range(Index.shape[0]):
        pj = A[Index[j]]
        distance = linalg.norm(pi - pj, ord=2, keepdims=True)
        
        if distance == 0:
            Pair.append([current_index, Index[j]])
            Index = np.delete(Index, j, 0)
            break

虽然此代码适用于我，但时间复杂度为 O(n^2)，其中 n == len(A)，我想知道是否有更有效的方法以较低的时间复杂度完成这项工作。感谢您的任何想法和帮助。

Answer 1

您可以使用字典来跟踪每个点的索引。

然后，您可以遍历字典中的项目，打印出与多次出现的点对应的索引。这个过程的运行时间是线性的，而不是二次的，在 A:

中的点数

points = {}

for index, point in enumerate(A):
    point_tuple = tuple(point)
    if point_tuple not in points:
        points[point_tuple] = []
    points[point_tuple].append(index)

for point, indices in points.items():
    if len(indices) > 1:
        print(indices)

打印出来：

[0, 3, 7]
[1, 6]

如果您只想要出现点的前两个索引，您可以使用 print(indices[:2]) 而不是 print(indices)。

Answer 2

这与另一个答案类似，但由于在多对的情况下您只需要前两个，因此您可以在一次迭代中完成。在字典中的适当键下添加索引，并在（且仅当）有两点时生成索引：

from collections import defaultdict

l = [[1, 1], [2, 3], [1, 4], [1, 1], [10, 3], [5, 2], [2, 3], [1, 1], [3, 4]]

def get_pairs(l):
    ind = defaultdict(list)

    for i, pair in enumerate(l):
        t = tuple(pair)
        ind[t].append(i)
        if len(ind[t]) == 2:
            yield list(ind[t])

list(get_pairs(l))
# [[0, 3], [1, 6]]

Answer 3

一个pure-Numpy没有循环的解决方案（迄今为止唯一的）是使用np.unique两次有一个技巧，就是删除在两次搜索之间找到的第一个项目。此解决方案假设可以设置 sentinel（例如 -1，整数的最小值，NaN），这通常不是问题（如果需要，您可以使用更大的类型）。

A = np.array([[1, 1], [2, 3], [1, 4], [1, 1], [10, 3], [5, 2], [2, 3], [1, 1], [3, 4]], dtype=int)

# Copy the array not to mutate it
tmp = A.copy()

# Find the location of unique values
pair1, index1 = np.unique(tmp, return_index=True, axis=0)

# Discard the element found assuming -1 is never stored in A
INT_MIN = np.iinfo(A.dtype).min
tmp[index1] = INT_MIN

# Find the location of duplicated values
pair2, index2 = np.unique(tmp, return_index=True, axis=0)

# Extract the indices that share the same pair of values found
left = index1[np.isin(pair1, pair2).all(axis=1)]
right = index2[np.isin(pair2, pair1).all(axis=1)]

# Combine the each left index with each right index
result = np.hstack((left[:,None], right[:,None]))

# result = array([[0, 3],
#                 [1, 6]])

此解决方案应在 O(n log n) 时间内运行，因为 np.unique 在内部使用基本排序（更具体地说 quick-sort） .

在不使用嵌套循环的情况下查找列表中所有对的有效方法

Efficient way to find all the pairs in a list without using nested loop

python

list

performance

search