Trouver l’ordre lexicographique d’une partition entière

Pour les permutations, étant donné N et k , j’ai une fonction qui trouve la k ème permutation de N dans l’ordre lexicographique. Aussi, étant donné une perm permutation, j’ai une fonction qui trouve l’indice lexicographique de la permutation parmi toutes les permutations de N Pour ce faire, j’ai utilisé la “décomposition factorielle” comme suggéré dans cette réponse .

Maintenant, je veux faire la même chose pour les partitions entières de N Par exemple, pour N=7 , je veux pouvoir aller et venir entre l’index (à gauche) et la partition (à droite):

  0 ( 7 ) 1 ( 6 1 ) 2 ( 5 2 ) 3 ( 5 1 1 ) 4 ( 4 3 ) 5 ( 4 2 1 ) 6 ( 4 1 1 1 ) 7 ( 3 3 1 ) 8 ( 3 2 2 ) 9 ( 3 2 1 1 ) 10 ( 3 1 1 1 1 ) 11 ( 2 2 2 1 ) 12 ( 2 2 1 1 1 ) 13 ( 2 1 1 1 1 1 ) 14 ( 1 1 1 1 1 1 1 ) 

J’ai essayé quelques petites choses. Le meilleur que j’ai trouvé était

 sum = 0; for (int i=0; i<length; ++i) sum += part[i]*i; return sum; 

ce qui donne ce qui suit:

  0 0( 7 ) 1 1( 6 1 ) 2 2( 5 2 ) 3 3( 5 1 1 ) 3 4( 4 3 ) 4 5( 4 2 1 ) 6 6( 4 1 1 1 ) 5 7( 3 3 1 ) 6 8( 3 2 2 ) 7 9( 3 2 1 1 ) 10 10( 3 1 1 1 1 ) 9 11( 2 2 2 1 ) 11 12( 2 2 1 1 1 ) 15 13( 2 1 1 1 1 1 ) 21 14( 1 1 1 1 1 1 1 ) 

Cela ne fonctionne pas tout à fait, mais semble être sur la bonne voie. Je suis venu avec cela parce que ça compte en quelque sorte le nombre de fois que je dois déplacer un nombre vers le bas (comme 6,3,2 va à 6,3,1,1 ). Cependant, je ne vois pas comment résoudre ce problème, car je ne sais pas comment rendre compte du moment où les choses doivent être recombinées (comme 6,3,1,1 passe à 6,2,2 ).

Pensez pourquoi la “décomposition factorielle” fonctionne pour les permutations, et la même logique fonctionne ici. Cependant, au lieu d’utiliser k! pour le nombre de permutations de k objects, vous devez utiliser la fonction de partition p(n,k) pour le nombre de partitions de n avec la plus grande partie au plus k . Pour n=7 , ces nombres sont:

 k | p(7,k) 0 | 0 1 | 1 2 | 4 3 | 8 4 | 11 5 | 13 6 | 14 7 | 15 

Pour obtenir l’index lexicographique de (3,2,1,1) , par exemple, vous calculez

 p(3+2+1+1) - [ p(3+2+1+1,3-1) + p(2+1+1,2-1) + p(1+1,1-1) + p(1,1-1) ] - 1 

qui est 15 - [4 + 1 + 0 + 0] - 1 = 9 . Ici, vous calculez le nombre de partitions de 7 dont la plus grande partie est inférieure à 3 plus le nombre de partitions de 4 dont la plus grande partie est inférieure à 2 plus … La même logique peut inverser cette tendance. En C, les fonctions (non testées!) Sont:

 int rank(int part[], int size, int length) { int r = 0; int n = size; int k; for (int i=0; i0) { for (k=0; kn) break; } parts[length++] = k; N -= k; n -= numPar(N,k-1); } return length; } 

Ici, numPar(int n) doit renvoyer le nombre de partitions de n , et numPar(int n, int k) doit renvoyer le nombre de partitions de n avec la plus grande partie au plus k . Vous pouvez les écrire vous-même à l’aide de relations de récurrence.

 #include  // number of combinations to divide by the number of k below n int partition(int n, int k){ int p,i; if(n<0) return 0; if(n<2 || k==1) return 1; for(p=0,i=1;i<=k;i++){ p+=partition(ni,i); } return p; } void part_nth_a(int n, int k, int nth){ if(n==0)return; if(n== 1 || n==k && nth == 0){ printf("%d ", n); return ; } int i, diff; for(i=0;i