获取关系列表中的位置

Question

我有一个元素集合。我可以像这样将每个元素与另一个元素联系起来：

> k=0; for (i=0;i<5;i++) {for (j=i+1;j<5;j++) { console.log(k++, ': ', i, '-', j) } }
0 :  0 - 1
1 :  0 - 2
2 :  0 - 3
3 :  0 - 4
4 :  1 - 2
5 :  1 - 3
6 :  1 - 4
7 :  2 - 3
8 :  2 - 4
9 :  3 - 4

我的问题是：

给定两个元素索引，如何获取关系列表中的位置？

例如，对于i=1和j=2，我想获得4。

该解决方案适用于任何大小的集合。

Answer 1

您描述的是2D array。只需添加：

var arr = new Array(5); // or n
k = 0;
for (i = 0; i < 5; i++) {
    arr[i] = new Array(5); // or n
    for (j = i + 1; j < 5; j++) {
         arr[i][j] = k;
         k++;
    }
}

你已经得到了你想要的。

Answer 2

假设有 n 个元素，我们正在寻找关系 i j。进一步假设i < j。我们想知道关系 i j 在关系列表中的位置；换句话说，我们想知道在关系列表中 i j 之前有多少关系 k l。

然后我们要回答两个问题：

在[0, ..., i-1]和l任何元素中，k有多少关系k l？
i l与l在[i+1, ..., j-1]中有多少关系？

第一个问题的答案是i * (i-1) / 2 + i * (n - i)。

第二个问题的答案是j - i - 1。

关系列表中的位置是这两个值的总和。

测试 python 中的正确性：

def get_position_in_relations_list(n, i, j):
  assert(j != i)
  if j < i:
    i,j = j,i
  return (i * (2 * n - i - 1)) // 2 + j - i - 1

n = 100
pos = 0
for i in range(n):
  for j in range(i+1,n):
    assert(pos == get_position_in_relations_list(n, i, j))
    pos += 1

获取关系列表中的位置

Get position in relation list

algorithm

performance

relation