восстановить индекс в треугольных для петель

Question

Есть ли простой способ восстановить индекс в вложенных циклах? Например, в течение петель, которые конструируют Треугольник Паскаля

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

есть способ восстановить i и j дал только index?

Answer 1

Я добавляю это как второй ответ, так как он находится на другом языке (теперь C) и имеет более прямой подход. Я сохраняю оригинальный ответ, так как следующий код почти необъяснимо без него. Я объединил две свои функции в одну, чтобы сократить накладные расходы на функции. Кроме того, чтобы быть на 100% уверенным, что он отвечает на исходный вопрос, я использовал петли из этого вопроса дословно. В функции драйвера я явно показываю, что вывод правильный для N = 4, а затем стресс-тест для N = 10000 (всего 100 000 000 проходов через внутренний цикл). У меня нет никакого формального кода времени, но на моей машине требуется около 1 секунды, чтобы проверить и проверить эти 100 миллионов случаев. Мой код предполагает 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! 

Answer 2

В данном конкретном случае мы имеем

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], мы увеличиваем/уменьшаем значение i и заменяем его до тех пор, пока в этом интервале не получим значение j. Этот цикл, вероятно, будет повторяться для максимального количества шагов (я подозреваю, что максимум три шага, но не в настроении, чтобы это доказать). Таким образом, это должно выполняться с помощью постоянного количества шагов.

В качестве альтернативы мы можем приблизительно j быть N/3, вместо нуля. Это приблизительно ожидаемое значение j (во всех возможных случаях), поэтому метод, вероятно, будет сходиться «быстрее» на локальном этапе поиска.

В общем случае вы делаете что-то очень похожее, то есть вы решаете поддельное уравнение и выполняете локальный поиск по всему решению.

Answer 3

Мне было легче найти I, J из индекса в следующей схеме номер:

0 
1 2 
3 4 5 
6 7 8 9 

Так как индексы спускаясь влево являются triangular numbers вида к * (к + 1)/2. Решая соответствующее квадратичное уравнение, я смог восстановить строку и столбец из индекса. Но - ваши петли дают что-то вроде этого:

0 1 2 3 
4 5 6 
7 8 
9 

, который хитрым. Можно было бы решить эту проблему напрямую, но учтите, что если вычесть каждое из этих чисел от 9 вы получите

9 8 7 6 
5 4 3 
2 1 
0 

это является исходный треугольник перевернут вверх дном и отражается в горизонтальном положении. Таким образом - я могу уменьшить проблему вашего треугольника до моего треугольника. Следующий код Python показывает, как это работает (единственное, что не совсем очевидно, это то, что в Python 3 // - целочисленное деление). Функция fromIndexHelper - это мое решение моей исходной проблемы треугольника, а fromIndex - это то, как я перекладываю ее на ваш треугольник.Чтобы проверить это, я первый напечатанный шаблон для индекса п = 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)