Récupérer l'index en triangulaire pour les boucles

Question

Existe-t-il un moyen simple de récupérer un index dans les boucles imbriquées? Par exemple, dans les boucles qui construisent triangle Pascals

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

est-il un moyen de récupérer i et j donné que index?

Answer 1

J'ajoute cela comme une deuxième réponse puisqu'elle est dans une langue différente (maintenant C) et a une approche plus directe. Je garde la réponse originale puisque le code suivant est presque inexplicable sans cela. J'ai combiné mes deux fonctions en une seule pour réduire les frais généraux d'appel de fonction. Aussi, pour être sûr à 100% qu'il répond à la question initiale, j'ai utilisé textuellement les boucles de cette question. Dans la fonction pilote, je montre explicitement que la sortie est correcte pour N = 4, puis je la soumets à un test de contrainte pour N = 10000 (avec un total de 100 000 000 passages dans la boucle interne). Je n'ai pas de code temporel officiel, mais il faut environ 1 seconde sur ma machine pour tester et tester ces 100 millions de cas. Mon code suppose un int 32 bits. Changer de long si nécessaire:

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

Sortie:

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

Dans ce cas particulier, nous avons

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) 

avec j dans l'intervalle [1,N-i].

Nous négligeons j et considérons cela comme une équation quadratique dans i. Ainsi, nous résolvons

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

Nous approximer i être le plus grand sur les deux solutions résultantes (ou Ceil de cette valeur, car négliger j a pour effet d'abaisser la valeur de i). Nous revenons à la version complète de l'équation et lui substituons l'approximation de la valeur i. Si j est en dehors de l'intervalle [1,N-i], nous augmentons/diminuons la valeur de i et nous ré-substituons jusqu'à ce que nous obtenions une valeur de j dans cet intervalle. Cette boucle va probablement se répéter pour un nombre d'étapes constant maximum (je suspecte un maximum de trois pas, mais pas d'humeur à le prouver). Donc, cela devrait être faisable en un nombre constant d'étapes. Comme alternative, nous pourrions approcher j pour être N/3, au lieu de zéro. C'est approximativement la valeur attendue de j (sur tous les cas possibles), ainsi la méthode convergera probablement plus vite à l'étape de recherche locale.

Dans le cas général, vous faites quelque chose de très similaire, c'est-à-dire que vous résolvez une fausse équation et que vous effectuez une recherche locale autour de la solution.

Answer 3

je l'ai trouvé plus facile de i trouver, j de l'indice dans le modèle de numéro suivant:

0 
1 2 
3 4 5 
6 7 8 9 

Depuis les indices allant sur la gauche sont les triangular numbers de la forme k * (k + 1)/2. En résolvant une équation quadratique appropriée, j'ai pu récupérer la ligne et la colonne de l'index. Mais - vos boucles donnent quelque chose comme ceci:

0 1 2 3 
4 5 6 
7 8 
9 

qui est plus délicat. Il pourrait être possible de résoudre ce problème directement, mais notez que si vous soustrayez chacun de ces numéros de 9 vous obtenez

9 8 7 6 
5 4 3 
2 1 
0 

ce est le triangle d'origine tourné à l'envers et réfléchie horizontalement. Ainsi - je peux réduire le problème de votre triangle à mon triangle. Le code Python suivant montre comment cela fonctionne (la seule chose pas tout à fait évidente est que dans Python 3 // est une division entière). La fonction fromIndexHelper est ma solution à mon problème de triangle d'origine et fromIndex est la façon dont je le déplace vers votre triangle.Pour le tester j'ai imprimé le motif d'index pour n = 4, puis les indices correspondants récupérés par ma fonction 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('') 

Sortie:

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)