Get position in relation list

Question

I have a collection of elements. I can relate each element with the other like this:

> 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

My question is:

Given two element indexes, how can I get the position in the relations list?

For example, for i=1 and j=2 I want to obtain 4.

The solution should work for collections of any size.

Answer 1

Assume there are n elements and we are looking for relation i j. Further assume that i < j. We want to know the positions of relation i j in the relations list; in other words, we want to know how many relations k l come before i j in the relations list.

Then we have to answer two questions:

• How many relations k l are there with k in [0, ..., i-1] and l any element?
• How many relations i l are there with l in [i+1, ..., j-1]?

The answer to the first question is i * (i-1) / 2 + i * (n - i).

The answer to the second question is j - i - 1.

The position in the relations list is the sum of these two values.

Test for correctness in 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

Answer 2

What you are describing is called 2D array. Just add:

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++;
    }
}

and you've got what you asked for.