Pour ce faire, vous devez d'abord créer et remplir un tableau à deux dimensions, que j'appellerai NVT pour "nombre de queues valides", pour enregistrer le nombre de "queues" valides qui commencent à une certaine position avec une valeur donnée. Par exemple, NVT [4][6] = 3, parce qu'une combinaison qui a 6 en position #4 peut se terminer de 3 façons distinctes : ( , 6, 7), ( , 6, 8), et ( , 6, 9).
- Pour peupler NVT commencez par NVT [ k ][ ], qui est juste une rangée de tous les 1. Puis revenez aux positions précédentes, par exemple, NVT [2][5] = NVT [3][6] + NVT [3][7] + NVT [3][8], car une "queue" commençant à la position 3 avec la valeur 5 sera constituée de ce 5 plus une "queue" commençant à la position 4 avec la valeur 6, 7 ou 8.
- Notez que nous ne nous soucions pas de savoir s'il existe une manière valide de atteindre une queue donnée. Par exemple, NVT [4][1] = 3 à cause des queues valides (1, 2), (1, 3) et (1, 4), même s'il n'y a pas d'autres queues valides. complet des combinaisons de la forme ( , 1, _).
Une fois que vous avez fait cela, vous pouvez calculer le rang d'une combinaison C comme suit :
- Pour la position #1, comptez toutes les queues valides commençant à la position #1 avec une valeur inférieure à C [1]. Par exemple, si C commence par 3, alors ce sera NVT [1][1] + NVT [1][2], représentant toutes les combinaisons qui commencent par 1 ou 2.
- Ensuite, faites de même pour toutes les positions suivantes. Celles-ci représenteront les combinaisons qui commencent de la même manière que C jusqu'à une position donnée, mais ont ensuite une valeur moindre à cette position.
- Par exemple, si C est (1, 3, 5, 8, 9), cela revient à
0 +
( NVT [2][1] + NVT [2][2]) +
( NVT [3][1] + NVT [3][2] + NVT [3][3] + NVT [3][4]) +
( NVT [4][1] + NVT [4][2] + NVT [4][3] + NVT [4][4] + NVT [4][5] + NVT [4][6] + NVT [4][7]) + ( NVT [5][1] + NVT [5][2] + NVT [5][3] + NVT [5][4] + NVT [5][5] + NVT [5][6] + NVT [5][7] + NVT [5][8]).
Inversement, vous pouvez trouver la combinaison C avec un rang donné r comme suit :
- Créer une variable temporaire rr pour "rang restant", initialement égal à r .
- Pour trouver C [1] - la valeur en position #1 - compter les queues valides en partant de la position #1, en commençant par la valeur la plus faible possible (à savoir 1), en s'arrêtant dès que celle-ci dépasse rr . Par exemple, puisque NVT [1][1] = 66 et NVT [1][2] = 27, la combinaison de rang 75 doit commencer par 2 (car 75 66 et 75 < 66 + 27). Ensuite, on soustrait cette somme de rr (dans ce cas, il reste 75 - 66 = 9).
- Faites ensuite de même pour toutes les positions suivantes, en veillant à garder à l'esprit la plus petite valeur possible compte tenu de ce qui se trouvait dans la position précédente. En poursuivant notre exemple avec r = 75, C [1] = 2, et rr = 9, nous savons que C [2] 3 ; et puisque NVT [2][3] = 23 > rr on trouve immédiatement que C [2] = 3.
Analyse de la complexité :
- Espace :
-
NVT nécessite O ( nk ) espace.
- Renvoyer une combinaison comme une longueur- k Le tableau nécessite par nature O ( k ) ; mais si nous renvoyons la combinaison une valeur à la fois (en invoquant une fonction de rappel ou en l'imprimant sur une console ou autre), alors le calcul lui-même ne dépend pas réellement de ce tableau, et nécessite seulement O (1) espace supplémentaire.
- En dehors de cela, tout le reste peut être géré en O (1) espace ; nous n'avons pas besoin de récursion ou de tableaux temporaires ou quoi que ce soit.
- C'est l'heure :
- Peuplement du site NVT prend O ( nkd ) temps. (Remarque : si d est supérieure à n alors nous pouvons simplement définir d égal à n .)
- Étant donné que NVT le calcul du rang d'une combinaison donnée prend le pire des cas. O ( nk ) temps.
- Étant donné que NVT le calcul de la combinaison avec un rang donné prend le pire des cas. O ( nk ) temps.
Note d'implémentation : les détails de ce qui précède sont un peu compliqués ; il serait facile d'obtenir une erreur de type "off-by-one", ou de mélanger deux variables, ou autre, si vous n'avez pas de données concrètes à examiner. Puisqu'il n'y a que 168 combinaisons valides pour votre exemple, je recommande de les générer toutes, afin de pouvoir les référencer pendant le débogage.
Optimisation supplémentaire possible : Si vous prévoyez n est assez grand, et que vous prévoyez de faire beaucoup de requêtes pour "classer" et "déclasser" des combinaisons, alors vous pourriez trouver utile de créer un deuxième tableau, que j'appellerai NVTLT pour "nombre de queues valides inférieur à", pour enregistrer le nombre de "queues" valides qui commencent à une certaine position avec une valeur moins de une valeur donnée. Par exemple, NVTLT [3][5] = NVT [3][1] + NVT [3][2] + NVT [3][3] + NVT [3][4], ou si vous préférez, NVTLT [3][5] = NVTLT [3][4] + NVT [3][4]. (Vous pouvez faire ceci comme une transformation in-place, en écrasant complètement NVT donc c'est un O ( nk ) passent sans espace supplémentaire). Utilisation de NVTLT au lieu de NVT pour vos requêtes vous permettra d'effectuer une recherche binaire des valeurs, plutôt qu'une recherche linéaire, ce qui vous donnera le pire des cas O ( k journal n ) au lieu de O ( nk ). Notez que cette optimisation est encore plus délicate que la précédente, donc même si vous avez l'intention d'effectuer cette optimisation, je vous recommande de commencer par la précédente, de la faire fonctionner parfaitement, puis d'ajouter cette optimisation.
