Как удалить несимметричные пары c в массиве numpy?

Question

Учитывая numpy Nx2 numpy массив data целых (мы можем предположить, что data не имеет повторяющихся строк), мне нужно сохранить только те строки, элементы которых удовлетворяют соотношению

(data[i,0] == data[j,1]) & (data[i,1] == data[j,0])

Например, с

import numpy as np
data = np.array([[1, 2], 
                 [2, 1],
                 [7, 3],
                 [6, 6],
                 [5, 6]])

Я должен вернуть

array([[1, 2], # because 2,1 is present
       [2, 1], # because 1,2 is present
       [6, 6]]) # because 6,6 is present

Один многословный способ сделать это -

def filter_symmetric_pairs(data):
  result = np.empty((0,2))
  for i in range(len(data)):
    for j in range(len(data)):
      if (data[i,0] == data[j,1]) & (data[i,1] == data[j,0]):
        result = np.vstack([result, data[i,:]])
  return result

, и я придумал более краткий:

def filter_symmetric_pairs(data):
  return data[[row.tolist() in data[:,::-1].tolist() for row in data]]

Может кто-нибудь предложить лучшую numpy идиому?

Answer 1

Вы можете отсортировать массивы, сохраняя содержимое строк, используя argsort как для исходного, так и для обратного массивов, а затем просто проверить, какие строки равны, и использовать это в качестве маски для среза data.

import numpy as np

data = np.array([[1, 2],
                 [2, 1],
                 [7, 3],
                 [6, 6],
                 [5, 6]])

data_r = data[:,::-1]
sorter = data.argsort(axis=0)[:,0]
sorter_r = data_r.argsort(axis=0)[:,0]
mask = (data.take(sorter, axis=0) == data_r.take(sorter_r, axis=0)).all(axis=1)

data[mask]

# returns:
array([[1, 2],
       [2, 1],
       [6, 6]])

Answer 2

Вот несколько различных методов, которые вы можете использовать для этого. Первое - это «очевидное» квадратичное c решение, которое простое, но может создать проблемы, если у вас большой входной массив. Второй должен работать, пока у вас нет огромного диапазона чисел на входе, и он имеет преимущество работы с линейным объемом памяти.

import numpy as np

# Input data
data = np.array([[1, 2],
                 [2, 1],
                 [7, 3],
                 [6, 6],
                 [5, 6]])

# Method 1 (quadratic memory)
d0, d1 = data[:, 0, np.newaxis], data[:, 1]
# Compare all values in first column to all values in second column
c = d0 == d1
# Find where comparison matches both ways
c &= c.T
# Get matching elements
res = data[c.any(0)]
print(res)
# [[1 2]
#  [2 1]
#  [6 6]]

# Method 2 (linear memory)
# Convert pairs into single values
# (assumes positive values, otherwise shift first)
n = data.max() + 1
v = data[:, 0] + (n * data[:, 1])
# Symmetric values
v2 = (n * data[:, 0]) + data[:, 1]
# Find where symmetric is present
m = np.isin(v2, v)
res = data[m]
print(res)
# [[1 2]
#  [2 1]
#  [6 6]]

Answer 3

Меня осенило другое решение, которое рассматривает data как список ребер ориентированного графа и фильтрует только двунаправленные ребра (моя задача, таким образом, эквивалентна обнаружению взаимных ребер в графе ):

def filter_symmetric_pairs(data):
  rank = max(data.flatten() + 1) 
  adj = np.zeros((rank, rank)) 
  adj[data[:,0], data[:,1]] = 1 # treat the coordinates as edges of directed graph, compute adjaciency matrix
  bidirected_edges = (adj == adj.T) & (adj == 1) # impose symmetry and a nonzero value
  return np.vstack(np.nonzero(bidirected_edges)).T # list indices of components satisfying the above constraint