Comment voulez-vous écrire cet algorithme pour les grandes combinaisons de la manière la plus compacte?

https://stackoverflow.com/questions/956542

12-09-2019
|

Question

Le nombre de combinaisons d'éléments de k qui peuvent être récupérés à partir des éléments de N est décrit par la formule suivante.

             N! 
c =  ___________________ 
       (k! * (N - k)!)

Un exemple serait le nombre de combinaisons de 6 Balls peut être tiré d'un tambour de 48 Balls à un tirage de loterie.

Optimiser cette formule pour fonctionner avec la complexité de O temps le plus petit

Cette question a été inspirée par le nouveau moteur de mathématiques WolframAlpha et le fait qu'il peut calculer des combinaisons extrêmement importantes très rapidement. par exemple. et une discussion ultérieure sur le sujet sur un autre forum.

http://www97.wolframalpha.com/input/?i = 20000000 + Choisissez + 15000000

Je posterai quelques informations / liens de cette discussion après certaines personnes prennent un coup de couteau à la solution.

Toute langue est acceptable.

La solution

Notez que WolframAlpha renvoie une "approximation décimale". Si vous n'avez pas besoin d'une précision absolue, vous pouvez faire la même chose en calculant les factorielles avec Stirling Approximation de .

Maintenant, l'approximation de Stirling nécessite l'évaluation de (n / e) ^ n, où e est la base du logarithme naturel, qui sera de loin la plus lente opération. Mais cela peut être fait en utilisant les techniques décrites dans un autre post stackoverflow.

Si vous utilisez double précision et répétée équarrissage pour accomplir la exponentiation, les opérations seront:

3 évaluations d'une approximation de Stirling, chacune nécessitant O (log N) multiplications et une évaluation de la racine carrée.
2 multiplications
1 divisions

Le nombre d'opérations pourrait probablement être réduit avec un peu d'intelligence, mais la complexité totale va être O (log n) avec cette approche. Assez facile à gérer.

EDIT: Il y a aussi lié à être beaucoup de littérature académique sur ce sujet, étant donné la façon dont ce calcul est commun. Une bonne bibliothèque universitaire pourrait vous aider à suivre vers le bas.

EDIT2: En outre, comme l'a souligné dans une autre réponse, les valeurs facilement déborder un double, donc un type à virgule flottante avec une précision très étendue devra être utilisé même pour des valeurs modérément élevées de k et n

Autres conseils

python: O (min [ k , n - k ] ²)

def choose(n,k):
    k = min(k,n-k)
    p = q = 1
    for i in xrange(k):
        p *= n - i
        q *= 1 + i
    return p/q

Analyse:

La taille de p et q augmente linéairement dans la boucle, si peut être considéré comme n-i et 1+i d'avoir une taille constante.
Le coût de chaque multiplication sera alors également augmenter de façon linéaire.
Cette somme de toutes les itérations devient une série arithmétique sur k.

Ma conclusion: O (k ²)

Si réécrite pour utiliser les nombres à virgule flottante, les multiplications seront des opérations atomiques, mais nous allons perdre beaucoup de précision. Il déborde même pour choose(20000000, 15000000). (Pas une grosse surprise, car le résultat serait autour de 0,2119620413 × 10 ^4.884.378).

def choose(n,k):
    k = min(k,n-k)
    result = 1.0
    for i in xrange(k):
        result *= 1.0 * (n - i) / (1 + i)
    return result

Je résous dans Mathematica :

Binomial[n, k]

L'homme, qui était facile ...

python:? approximation en O (1)

En utilisant la mise en œuvre décimale de python pour calculer une approximation. Comme il ne l'utilise pas de boucle externe, et les chiffres sont limités en taille, je pense qu'il exécutera dans O (1).

from decimal import Decimal

ln = lambda z: z.ln()
exp = lambda z: z.exp()
sinh = lambda z: (exp(z) - exp(-z))/2
sqrt = lambda z: z.sqrt()

pi = Decimal('3.1415926535897932384626433832795')
e = Decimal('2.7182818284590452353602874713527')

# Stirling's approximation of the gamma-funciton.
# Simplification by Robert H. Windschitl.
# Source: http://en.wikipedia.org/wiki/Stirling%27s_approximation
gamma = lambda z: sqrt(2*pi/z) * (z/e*sqrt(z*sinh(1/z)+1/(810*z**6)))**z

def choose(n, k):
  n = Decimal(str(n))
  k = Decimal(str(k))
  return gamma(n+1)/gamma(k+1)/gamma(n-k+1)

Exemple:

>>> choose(20000000,15000000)
Decimal('2.087655025913799812289651991E+4884377')
>>> choose(130202807,65101404)
Decimal('1.867575060806365854276707374E+39194946')

Tout supérieur, et il va déborder. L'exposant semble se limiter à 40.000.000.

Étant donné un nombre raisonnable de valeurs pour n et K, les calculer à l'avance et utiliser une table de consultation.

Il est en esquivant la question d'une certaine façon (vous déchargeant le calcul), mais il est une technique utile si vous éprouvez de déterminer un grand nombre de valeurs.

Matlab:

la manière (en utilisant la fonction intégrée du tricheur
Je sais que c'est une question très ancienne, mais je me débattais avec une solution à ce problème depuis longtemps jusqu'à ce que je trouve un très simple écrit en VB 6 et après l'avoir porté à C #, est ici le résultat:
```
public int NChooseK(int n, int k)
{
    var result = 1;
    for (var i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }

    return result;
}
```
Le code final est si simple que vous ne croyez pas cela fonctionnera jusqu'à ce que vous l'exécutez.
En outre, le article originale donne une bonne explication sur la façon dont il a atteint l'algorithme final .

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow