Existe-t-il un meilleur algorithme pour affecter des nombres à des combinaisons?

Question

Il est bien connu que l'identité de Pascal peut être utilisé pour coder une combinaison de k éléments de n en nombre 0-(n \choose k) - 1 (nous allons appeler ce numéro un indice de combinaison ) en utilisant un combinatorial number system. En supposant un temps constant pour les opérations arithmétiques, cet algorithme prend le temps O (n). ^{& dagger;}

Je une application où k «n et un algorithme en O (n ) Il est infaisable. Y at-il un algorithme pour attribuer bijective un nombre compris entre 0 et (n \choose k) - 1 à une combinaison de k éléments de n dont l'exécution est d'ordre O (k ) ou similaire? L'algorithme n'a pas besoin de calculer le même mappage que le système de numéro combinatoire, cependant, l'inverse doit être calculable dans une complexité de temps similaire.

---

& dagger;   Plus précisément, l'algorithme calculant la combinaison à partir de l'index de combinaison s'exécute en O (n). Le calcul de l'index de combinaison à partir de la combinaison fonctionne en O (k) si vous précalculez les coefficients binomiaux.

Answer 1

Description d'un commentaire.

Pour l'index combinatoire donné (N), pour trouver k'th chiffres, il est nécessaire de trouver c_k telle que (c_k \choose k) <= N et ((c_k+1) \choose k) > N.

Définissez P(i,k) = i!/(i-k)!.

P(i, k) = i * (i-1) * ... * (i-k+1) 
substitute x = i - (k-1)/2 
    = (x+(k-1)/2) * (x+(k-1)/2-1) * ... * (x-(k-1)/2+1) * (x-(k-1)/2) 
    = (x^2 - ((k-1)/2)^2) * (x^2 - ((k-1)/2-1)^2) * ... 
    = x^k - sum(((k-2i-1)/2)^2))*x^(k-2) + O(x^(k-4)) 
    = x^k - O(x^(k-2)) 
P(i, k) = (i - (k-1)/2)^k - O(i^(k-2)) 

De l'inégalité ci-dessus:

(c_k \choose k) <= N 
P(c_k, k) <= N * k! 
c_k ~= (N * k!)^(1/k) + (k-1)/2 

Je ne suis pas sûr de la taille est O (C_K^(k-2)) partie. Je suppose que cela n'influence pas trop. Si c'est de l'ordre (c_k+1)/(c_k-k+1) que l'approximation est très bonne. Cela est dû:

((c_k+1) \choose k) = (c_k \choose k) * (c_k + 1)/(c_k - k + 1) 

Je voudrais essayer quelque chose comme algorithme:

For given k 
Precalculate k! 

For given N 
For i in (k, ..., 0) 
    Calculate c_i with (N * i!)^(1/i) + (i-1)/2 
    (*) Check is P(c_i, k) <=> N * i! 
    If smaller check c_i+1 
    If larger check c_i-1 
    Repeat (*) until found P(c_i, i) <= N * i! < P(c_i+1, i) 
    N = N - P(c_i, i) 

Si approximation est bonne, number of steps << k, que de trouver un chiffre est O (k).