在三角形 for 循环中恢复索引

Question

有没有简单的方法来恢复嵌套for循环中的索引？例如，在构造 Pascals 三角形

的 for 循环中

int index = 0;
for (int i = 0; i < N; ++i)
  for (int j = 0; j < N-i; ++j)
    index++;

有没有办法恢复 i 和 j 仅给出 index？

Answer 1

在这种特殊情况下，我们有

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)

和 j 区间 [1,N-i]。

我们忽略j并将其视为i中的二次方程。这样我们就解决了

-i^i/2 + (2N-1)i/2 + (1-index) = 0.

我们将 i 近似为两个结果解中的最大值（或该值的上限，因为忽略 j 会降低 i 的值).

然后我们回到方程的完整版本并代入 i 的近似值。如果 j 在区间 [1,N-i] 之外，我们 increase/decrease 的值 i 并重新代入，直到我们在这个区间内得到 j 的值。这个循环可能会重复最大数量的步骤（我怀疑最多三个步骤，但没有心情证明它）。所以这应该可以在恒定数量的步骤中完成。

作为替代方案，我们可以将 j 近似为 N/3，而不是零。这大约是 j 的预期值（在所有可能的情况下），因此该方法可能会在局部搜索步骤收敛 'faster'。

在一般情况下，您会做一些非常相似的事情，即您求解一个假方程并围绕该解执行局部搜索。

Answer 2

我发现从以下数字模式的索引中更容易找到 i,j:

因为向左下方的索引是 triangular numbers 形式的 k*(k+1)/2。通过求解一个适当的二次方程，我能够从索引中恢复行和列。但是——你的循环给出这样的东西：

这更棘手。或许可以直接解决这个问题，但请注意，如果你从 9 中减去这些数字中的每一个，你会得到

这个是原来的三角形倒过来倒过来倒映成水平的。因此——我可以将你的三角形问题归结为我的三角形问题。下面的 Python 代码显示了它是如何工作的（唯一不太明显的是 Python 3 // 中的整数除法）。函数 fromIndexHelper 是我对原始三角形问题的解决方案，而 fromIndex 是我将其转移到您的三角形的方法。为了测试它，我首先打印了 n = 4 的索引模式，然后通过我的函数 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('')

输出：

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)

Answer 3

我将其添加为第二个答案，因为它使用不同的语言（现在是 C）并且具有更直接的方法。我保留原始答案，因为没有它，以下代码几乎无法解释。我将我的两个函数合并为一个函数以减少函数调用开销。此外，为了 100% 确定它回答了原始问题，我逐字使用了该问题中的循环。在驱动程序函数中，我明确显示 N = 4 的输出是正确的，然后对 N = 10000 进行压力测试（总共有 100,000,000 次通过内部循环）。我没有任何正式的计时代码，但在我的机器上运行需要大约 1 秒的时间来测试这 1 亿个案例。我的代码采用 32 位 int。如果需要，更改为 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;   
}

输出：

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!

在三角形 for 循环中恢复索引

recover index in triangular for loops

math

discrete-mathematics

indices