Reconstruct triangular index for loops
I am adding this as a second answer as it is in a different language (now C) and has a more direct approach. I keep the original answer as the following code is almost inexplicable without it. I have combined my two functions into one to reduce function overhead. Also, to be 100% sure that it answers the original question, I used the loops from this question verbatim. In the driver function, I explicitly show that the output is correct for N = 4, and then stress test for N = 10,000 (total 100,000,000 passes through the inner loop). I don't have any formal time code, but it takes about 1 second on my machine to check and verify these 100 million cases. My code assumes 32-bit int
. Change to long
:
#include <stdio.h>
#include <math.h>
void from_index(int n, int index, int *i, int *j);
int main(void){
int N;
int ri,rj; //recovered i,j
N = 4;
int index = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N-i; ++j){
from_index(N,index,&ri,&rj);
printf("i = %d, j = %d, index = %d, ",i,j,index);
printf("recovered i = %d, recovered j = %d\n",ri,rj);
index++;
}
//stress test:
N = 10000;
index = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N-i; ++j){
from_index(N,index,&ri,&rj);
if(i != ri || j != rj){
printf("Don't post buggy code to Stack Overflow!\n");
printf("(i,j) = (%d,%d) but recovered indices are (%d,%d)\n",i,j,ri,rj);
return 0;
}
index++;
}
printf("\nAll %d tests passed!\n",N*N);
return 0;
}
void from_index(int n, int index, int *i, int *j){
double d;
d = 4*n*(n+1) - 7 - 8 * index;
*i = floor((-1 + sqrt(d))/2);
*j = *i * (*i + 1)/2;
*j = n*(n+1)/2 - 1 - index - *j;
*j = *i - *j;
*i = n - *i - 1;
}
Output:
i = 0, j = 0, index = 0, recovered i = 0, recovered j = 0 i = 0, j = 1, index = 1, recovered i = 0, recovered j = 1 i = 0, j = 2, index = 2, recovered i = 0, recovered j = 2 i = 0, j = 3, index = 3, recovered i = 0, recovered j = 3 i = 1, j = 0, index = 4, recovered i = 1, recovered j = 0 i = 1, j = 1, index = 5, recovered i = 1, recovered j = 1 i = 1, j = 2, index = 6, recovered i = 1, recovered j = 2 i = 2, j = 0, index = 7, recovered i = 2, recovered j = 0 i = 2, j = 1, index = 8, recovered i = 2, recovered j = 1 i = 3, j = 0, index = 9, recovered i = 3, recovered j = 0 All 100000000 tests passed!
source to share
In this particular case, we have
index = N+(N-1)+...+(N-i+1) + (j+1) = i(2N-i+1)/2 + (j+1) = -i^i/2 + (2N-1)i/2 + (j+1)
s j
in the interval [1,N-i]
.
We neglect j
and treat this as a quadratic equation in i
. So we decide
-i^i/2 + (2N-1)i/2 + (1-index) = 0.
We approach i
the largest of the two resulting solutions (or the limit value of this value, since neglect j
leads to a decrease in the value i
).
We then go back to the full version of the equation and substitute an approximation for the value i
. If it j
is outside the interval [1,N-i]
, we increase / decrease the value i
and substitute again until we get a value j
in that interval. This cycle will probably repeat itself for as many steps as possible (I suspect three steps at most, but not in the mood to prove it). Thus, this must be done with a constant number of steps.
Alternatively, we could approximate j
as N/3
instead of zero. This is roughly the expected value j
(in all possible cases), so the method is likely to converge "faster" in the local search step.
In general, you are doing something very similar, that is, you are solving the fake equation and doing a local search for the solution.
source to share
I found it easier to find i, j from index in the following number pattern:
0
1 2
3 4 5
6 7 8 9
Since the indices going to the left are triangular numbers of the form k * (k + 1) / 2. By solving the corresponding quadratic equation, I was able to recover the row and column from the index. But - your loops give something like this:
0 1 2 3
4 5 6
7 8
9
which is more difficult. It might be possible to solve this problem directly, but note that if you subtract each of these numbers from 9, you get
9 8 7 6
5 4 3
2 1
0
it is the original triangle, turned upside down and reflected horizontally. This way - I can reduce your triangle problem to my triangle. The following Python code shows how it works (the only thing that's not entirely obvious is that //
there is integer division in Python 3 ). The function fromIndexHelper
is my solution to my original triangle problem, and fromIndex
this is how I translate it into your triangle. To test this, I first printed the index pattern for n = 4, and then the corresponding indexes recovered by my function fromIndex
:
from math import floor, sqrt
def fromIndexHelper(n,index):
i = floor((-1+sqrt(1+8*index))/2)
j = index - i*(i+1)//2
return i,j
def fromIndex(n,index):
shift = n*(n+1)//2 - 1
i,j = fromIndexHelper(n,shift-index)
return n-i-1,i - j
#test
index = 0
for i in range(4):
for j in range(4-i):
print(index,end = ' ')
index +=1
print('')
print(' ')
index = 0
for i in range(4):
for j in range(4-i):
print(fromIndex(4,index),end = ' ')
index +=1
print('')
Output:
0 1 2 3
4 5 6
7 8
9
(0, 0) (0, 1) (0, 2) (0, 3)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1)
(3, 0)
source to share