Предположим, что у вас есть симметричная матрица расстояний A. Например A является 4*4 (цифры выше и слева от матрицы индексов элементов, между которыми измеряется расстояние, и мы используем только нижний треугольник):Доступ к элементам упакованной симметричной матрицы расстояний
0 1 2 3
_____________
0 |0 0 0 0
1 |a10 0 0 0
2 |a20 a21 0 0
3 |a30 a31 a32 0
Так, в принципе, если A является n*n, у нас есть только n*(n-1)/2 полезных записей. Устранение нулей на диагонали, мы имеем следующую матрицу (аналогичный тому, что есть Matlab и R):
A= 0 1 2
_________
1 |a10 0 0
2 |a20 a21 0
3 |a30 a31 a32
Далее, мы можем эффективно хранить эту матрицу в одномерный массив в упакованном формате, имеющего np = n*(n-1)/2 элементы:
Ap = {a10, a20, a21, a30, a31, a32}
Это может ускорить много поисков (например, поиск для пары ближайших элементов и т.д.) и сэкономить много места (полезно, когда n велико)
Доступ расстояния между элементами i и j эквивалентно доступу к элементу j+i(i-1)/2 в упакованной матрице, то есть A[i,j] = Ap[j+i(i-1)/2] для i>0, j<n-1, j<i.
Вопрос заключается в том, если мы находимся в противоположной ситуации, то есть у нас есть индекс элемента в упакованной матрице Ap, как мы восстановить исходные два индекс: Учитывая Ap[x], какова i и j в A, такие это Ap[x] = A[i,j].
Спасибо!