Nombre de n-élément de permutations avec exactement k inversions

C'est un jour plus tard, et j'ai réussi à résoudre le problème en utilisant la programmation dynamique. Je l'ai soumis et mon code a été accepté par SPOJ donc je me dis que je vais partager mes connaissances ici pour quiconque est intéressé à l'avenir.

Après avoir cherché dans l' Page Wikipedia qui traite de l'inversion en mathématiques discrètes, j'ai trouvé une intéressante recommandation au bas de la page.

Nombre de permutations de n éléments avec k inversions; Mahonian
numéros: A008302

J'ai cliqué sur le lien pour OEIS et il m'a montré une suite infinie d'entiers appelé le Triangle de Mahonian numéros.

1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 6, 5, 3, 1, 1, 4, 9, 15, 20, 22, 20, 15,
9, 4, 1, 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1,
1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359,
259, 169, 98, 49, 20, 6, 1 . . .

J'étais curieux de savoir ce que ces chiffres, car ils semblaient familier pour moi. Puis j'ai réalisé que j'avais vu que la sous-suite 1, 3, 5, 6, 5, 3, 1 avant de. En fait, c'était la solution du problème pour plusieurs couples (n, k), à savoir (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6). J'ai regardé ce qui était sur les deux côtés de cette sous-suite et a été étonné de voir qu'il était valide (c'est à dire supérieure à 0 permutations) réponses pour le n < 4 et n > 4.

La formule pour la séquence a été donnée sous la forme:

coefficients d'expansion de Product_{i=0..n-1} (1+x+...+x^i)

C'était assez facile pour moi de comprendre et de vérifier. Je pourrais en gros, prendre tout n et de le brancher dans la formule. Le coefficient pour la x^k terme serait la solution pour (n, k).

Je vais vous montrer un exemple pour n = 3.

(x0)(x0 + 1)(x0 + x1 + x2)
= (1)(1 + x)(1 + x + x2)
= (1 + x)(1 + x + x2)
= 1 + x + x + x2 + x2 + x3
= 1 + 2x + 2x2 + x3

La dernière extension a été 1 + 2x + 2x2 + x3 et les coefficients de x^k conditions étaient de 1, 2, 2, et 1 pour k = 0, 1, 2, 3 respectivement. Cela se produit juste pour être valide tous les numéros de inversions pour les 3-élément de permutations.

1, 2, 2, 1 est la 3ème ligne de la Mahonian numéros lorsqu'ils sont disposés dans un tableau comme suit:

1
1 1
1 2 2 1
1 3 5 6 5 3 1
etc.

Donc, fondamentalement, le calcul de ma réponse se résume simplement à calculer le n-ième Mahonian de ligne et prendre la kième élément k de départ à 0 et l'impression de 0 si l'index est hors de la plage. C'était une simple affaire de bottom-up de la programmation dynamique, puisque chaque i-ème ligne pourrait être utilisé pour calculer facilement le i+1ère ligne.

Donné ci-dessous est le Python solution que j'ai utilisé qui a couru seulement 0,02 secondes. Le délai maximal pour que ce problème était de 3 secondes pour leur donné des cas de test et j'ai été faire une erreur de dépassement de délai avant, donc je pense que cette optimisation est plutôt bonne.

def mahonian_row(n):
    '''Generates coefficients in expansion of 
    Product_{i=0..n-1} (1+x+...+x^i)
    **Requires that n is a positive integer'''
    # Allocate space for resulting list of coefficients?
    # Initialize them all to zero?
    #max_zero_holder = [0] * int(1 + (n * 0.5) * (n - 1))

    # Current max power of x i.e. x^0, x^0 + x^1, x^0 + x^1 + x^2, etc.
    # i + 1 is current row number we are computing
    i = 1
    # Preallocate result
    # Initialize to answer for n = 1
    result = [1]
    while i < n:
        # Copy previous row of n into prev
        prev = result[:]
        # Get space to hold (i+1)st row
        result = [0] * int(1 + ((i + 1) * 0.5) * (i))
        # Initialize multiplier for this row
        m = [1] * (i + 1)
        # Multiply
        for j in range(len(m)):
            for k in range(len(prev)):
                result[k+j] += m[j] * prev[k]
        # Result now equals mahonian_row(i+1)
        # Possibly should be memoized?
        i = i + 1
    return result


def main():
    t = int(raw_input())
    for _ in xrange(t):
        n, k = (int(s) for s in raw_input().split())
        row = mahonian_row(n)
        if k < 0 or k > len(row) - 1:
            print 0
        else:
            print row[k]


if __name__ == '__main__':
    main()

Je n'ai aucune idée de la complexité du temps, mais je suis absolument certain de ce code peut être amélioré grâce à memoization depuis il y a 10 compte tenu des cas de test et les calculs pour les précédents cas de test peut être utilisé pour "tricher" sur l'avenir de cas de test. Je vais faire cette optimisation dans l'avenir, mais j'espère que cette réponse dans son état actuel permettra à quiconque de tenter ce problème à l'avenir, car elle évite les naïfs factorielle-la complexité de l'approche de la production et de l'itération sur toutes les permutations.

Un problème majeur dans le calcul de ces coefficients est la taille de la commande du produit résultant. Le polynôme Produit i=1,2,..,n {(1+x).(1+x+x^2)....(1+x+x^2+..+x^i)+...(1+x+x^2+...+x^n), aura un ordre équivalent à n*(n+1). Par conséquent, cela met un restrictive de calcul de limite sur le processus. Si nous utilisons un processus où les résultats précédents pour le Produit de n-1 sont utilisés dans le processus de calcul du Produit de n, nous sommes à la recherche à la de stockage de (n-1)*n entiers. Il est possible d'utiliser un processus récursif, ce qui sera beaucoup plus lente, et encore, il est limité aux entiers inférieurs à la racine carrée de la commune de la taille de l'entier. La suite est un peu rugueuse et prêt récursive code pour ce problème. La fonction mahonian(r,c) retourne le c th coefficient pour la r th Produit. Mais là encore, c'est extrêmement lent pour les grands Produits de plus de 100. L'exécution de ce qu'il peut être vu que la récursivité est clairement pas la réponse.

unsigned int numbertheory::mahonian(unsigned int r, unsigned int c)
  {
      unsigned int result=0;
      unsigned int k;

     if(r==0 && c==0)
       return 1;
     if( r==0 && c!=0)
      return 0;

   for(k=0; k <= r; k++)
       if(r > 0 && c >=k)
           result = result + mahonian(r-1,c-k);

   return result;

}

Comme une question d'intérêt, j'ai inclus le suivant qui est une version c++ de Sashank qui est beaucoup plus rapide que mon exemple de récursivité. Remarque-je utiliser le tatou de la bibliothèque.

uvec numbertheory::mahonian_row(uword n){
 uword i = 2;
 uvec current;
 current.ones(i);
 uword current_size;
 uvec prev;
 uword prev_size;

 if(n==0){
   current.ones(1);
   return current;
 }

 while (i <= n){                  //increment through the rows
   prev_size=current.size();     //reset prev size to current size
   prev.set_size(prev_size);     //set size of prev vector
   prev= current;                //copy contents of current to prev vector
   current_size =1+ (i*(i+1)/2);      //reset current_size
   current.zeros(current_size);    //reset current vector with zeros

   for(uword j=0;j<i+1; j++)       //increment through current vector
      for(uword k=0; k < prev_size;k++)
         current(k+j) += prev(k);
   i++;                                        //increment to next row
}
return current;                                //return current vector
 }

 uword numbertheory::mahonian_fast(uword n, uword c) {
**This function returns the coefficient of c order of row n of
**the Mahonian numbers
    //check for input errors
    if(c >= 1+ (n*(n+1)/2)) {
        cout << "Error. Invalid input parameters" << endl;
   }
   uvec mahonian;
   mahonian.zeros(1+ (n*(n+1)/2));
   mahonian = mahonian_row(n);
   return mahonian(c);
 }