Как преобразовать скалярный индекс в двумерный индекс в numpy - PullRequest
Новая
       46

Как преобразовать скалярный индекс в двумерный индекс в numpy

0 голосов
/ 30 апреля 2020

Допустим, у нас есть набор из N узлов, которые могут быть связаны, как в сложной сети, и нам не важно направление соединения (поэтому связь между 1 и 2 такая же, как 2 и 1). ).

Я хочу использовать одномерный массив numpy для представления состояния каждой ссылки. Состояние принимает значения в {1,0}, где 1 означает, что ссылка существует. Массив, назовем его «состоянием», должен иметь длину N * (N-1) / 2, я полагаю (исключаются автоциклы).

В таком контексте, как я могу правильно проиндексировать все ссылки, которые начинаются в узле a, или ссылки, которые заканчиваются в узле b? Если мы назовем массив «состояниями», я бы сказал, что состояние [i] = состояние ссылки, которая начинается в узле a или заканчивается в узле j. Есть ли способ, возможно, эффективный способ сделать это? Если у нас N = 10 узлов, первые 8 записей соответствуют ссылкам, начиная с узла 1 и заканчивая узлами 2,3,4, ..., 10, но я не могу найти общий способ express этого. Спасибо.

Ps: я знаю, что 2D-матрица может быть более полезной, но для моих целей я бы хотела решить проблему с сохранением состояний в одномерном массиве.

1 Ответ

0 голосов
/ 01 мая 2020

Индекс для пары узлов (a, b) может быть вычислен с использованием переменной base, определяемой количеством предшествующих элементов для меньшего из двух идентификаторов узлов. Добавление большего к этой базе дает правильный индекс:

Вы можете создать функцию для получения индекса состояния из пары идентификаторов узлов (на основе нуля), например: 

def indexOf(a,b,N=10):
    return indexOf(b,a,N) if a>b else N*a-a*(a+1)//2+b

производит индексы в соответствии с запросом: 

for a in range(10):
    print([indexOf(a,b) for b in range(10)])

[0, 1,  2,  3,  4,  5,  6,  7,  8,  9]
[1, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[2, 11, 19, 20, 21, 22, 23, 24, 25, 26]
[3, 12, 20, 27, 28, 29, 30, 31, 32, 33]
[4, 13, 21, 28, 34, 35, 36, 37, 38, 39]
[5, 14, 22, 29, 35, 40, 41, 42, 43, 44]
[6, 15, 23, 30, 36, 41, 45, 46, 47, 48]
[7, 16, 24, 31, 37, 42, 46, 49, 50, 51]
[8, 17, 25, 32, 38, 43, 47, 50, 52, 53]
[9, 18, 26, 33, 39, 44, 48, 51, 53, 54]

allPairs = [ (a,b) for a in range(10) for b in range(a,10) ]
print( sorted(allPairs,key=lambda ab:indexOf(*ab) ) )
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (6, 6), (6, 7), (6, 8), (6, 9), (7, 7), (7, 8), (7, 9), (8, 8), (8, 9), (9, 9)]

Обратите внимание, что это распределяет записи для ссылок на узлы сами по себе

Недостаток этой модели индексации заключается в том, что для нее требуется, чтобы число узлы (N) должны быть известны заранее и предоставляться при каждом вызове.

Более общий подход c заключается в том, чтобы индексировать плоский список по-разному в зависимости от последовательности, не требующей наличия заранее определенного значения для N. Каждая пара всегда будет иметь одинаковый индекс независимо от общего числа. узлов: 

def indexOf(a,b):
    return indexOf(b,a) if a<b else a*(a+1)//2+b

его можно изменить (чтобы получить пару узлов по заданному индексу) следующим образом: 

def unindex(X):
    b = int( ((8*X+1)**0.5-1)/2 )
    a = X - b*(b+1)//2
    return a,b

Индексы не в том же порядке, но функция не нужно знать N: 

for a in range(10):
    print([indexOf(a,b) for b in range(10)])

[0,  1,  3,  6,  10, 15, 21, 28, 36, 45]
[1,  2,  4,  7,  11, 16, 22, 29, 37, 46]
[3,  4,  5,  8,  12, 17, 23, 30, 38, 47]
[6,  7,  8,  9,  13, 18, 24, 31, 39, 48]
[10, 11, 12, 13, 14, 19, 25, 32, 40, 49]
[15, 16, 17, 18, 19, 20, 26, 33, 41, 50]
[21, 22, 23, 24, 25, 26, 27, 34, 42, 51]
[28, 29, 30, 31, 32, 33, 34, 35, 43, 52]
[36, 37, 38, 39, 40, 41, 42, 43, 44, 53]
[45, 46, 47, 48, 49, 50, 51, 52, 53, 54]

print( [unindex(x) for x in range(N*(N+1)//2) ])
[(0, 0), (0, 1), (1, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3), (2, 3), (3, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (0, 6), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6), (6, 6), (0, 7), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (0, 8), (1, 8), (2, 8), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8), (8, 8), (0, 9), (1, 9), (2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9), (9, 9)]

Используя numpy, если у вас есть массив пар узлов, вы можете получить их соответствующие индексы состояния, написав функцию (2-я версия) следующим образом: 

import numpy as np

def indexOf(ab):
    a,b = np.max(ab,axis=-1),np.min(ab,axis=-1)
    return a*(a+1)//2 + b

вывод: 

N = 10

states = np.arange(N*(N+1)//2)%2        # some random node links

pairs = np.array( [[1,3],[2,4],[7,2]] ) # array of node pairs

connected= states[indexOf(pairs)]       # indirection to states

print(states)
# [0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0]
print(indexOf(pairs))
# [ 7 12 30]
print(connected)
# [1 0 0]

если вы используете первую версию функции, вам нужно будет передавать число узлов при каждом вызове: 

def indexOf(ab,N=10):
    a,b = np.min(ab,axis=-1),np.max(ab,axis=-1)
    return N*a-a*(a+1)//2+b

connected= states[indexOf(pairs,N=10)]
...