¿Cómo se escribe este algoritmo para grandes combinaciones de la forma más compacta?

StackOverflow https://stackoverflow.com/questions/956542

Pregunta

El número de combinaciones de elementos k que se pueden recuperar de artículos N se describe por la siguiente fórmula. 

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

Un ejemplo podría ser el número de combinaciones de 6 Balls se puede sacar de un tambor de 48 Balls en un sorteo de la lotería.

Optimizar esta fórmula para funcionar con la complejidad menor tiempo O

Esta pregunta se inspiró en el nuevo motor de matemáticas WolframAlpha y el hecho de que se pueda calcular extremadamente grandes combinaciones muy rápidamente. p.ej. y una discusión posterior sobre el tema en otro foro.

  

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

Voy a publicar algunos detalles / enlaces de esa discusión después de que algunas personas toman una puñalada en la solución.

Cualquier lenguaje es aceptable.

¿Fue útil?

Solución

Tenga en cuenta que WolframAlpha devuelve una "aproximación decimal". Si usted no necesita una precisión absoluta, se podría hacer lo mismo mediante el cálculo de los factoriales con aproximación de Stirling .

Ahora, la aproximación de Stirling requiere la evaluación de (n / e) ^ n, donde e es la base del logaritmo natural, que será, de lejos, la operación más lenta. Pero esto se puede hacer usando las técnicas descritas en otro post stackOverflow .

Si utiliza doble precisión y repetidas cuadratura para realizar la exponenciación, las operaciones serán los siguientes:

  • 3 evaluaciones de una aproximación Stirling, cada O requiere (log n) multiplicaciones y una evaluación de raíz cuadrada.
  • 2 multiplicaciones
  • 1 divisiones

El número de operaciones probablemente podría reducirse con un poco de inteligencia, pero la complejidad tiempo total va a ser O (log n) con este enfoque. Bastante manejable.

EDIT: También hay destinada a ser una gran cantidad de literatura académica sobre este tema, teniendo en cuenta lo común este cálculo es. Una buena biblioteca universitaria podría ayudarle a rastrear hacia abajo.

Edit2: También, como se ha señalado en otra respuesta, los valores se desbordarán fácilmente un así un tipo de punto doble, flotante con precisión muy extendido tendrá que ser utilizado para incluso moderadamente grandes valores de k y n

.

Otros consejos

Python: O (min [ k , n - k ] 2 ) 

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

Análisis:

  • El tamaño de p y q aumentará linealmente dentro del bucle, si n-i y 1+i pueden considerarse que tienen tamaño constante.
  • El costo de cada multiplicación será entonces también aumentar linealmente.
  • Esta suma de todas las iteraciones se convierte en una serie aritmética sobre k.

Mi conclusión: O (k 2 )

Si reescrito para utilizar números de punto flotante, las multiplicaciones serán operaciones atómicas, pero perderán mucha precisión. Incluso se desborda por choose(20000000, 15000000). (No es una gran sorpresa, ya que el resultado sería de alrededor de 0,2119620413 × 10 4884378 .) 

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

Me resuelvo en Mathematica : 

Binomial[n, k]

El hombre, que era fácil ...

Python:? aproximación en O (1)

Uso de la aplicación de pitón decimal para calcular una aproximación. Ya que no utiliza ningún tipo de bucle externo, y los números son de tamaño limitado, creo que va a ejecutar en 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)

Ejemplo: 

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

Más arriba, y se desbordará. El exponente parece estar limitada a 40 millones.

Dado un número razonable de valores para n y K, calcular de antemano y utilizar una tabla de consulta.

Es esquivando el tema de alguna manera (que está descargando el cálculo), pero es una técnica útil si va a tener para determinar un gran número de valores.

MATLAB:

  • El camino del tramposo (utilizando la función incorporada NCHOOSEK ):? 13 caracteres, O () 

    nchoosek(N,k)

  • Mi solución: 36 caracteres, O (min (k, N-k)) 

    a=min(k,N-k);
prod(N-a+1:N)/prod(1:a)

Sé que esto es una pregunta muy viejo, pero tuve problemas con una solución a este problema durante mucho tiempo hasta que me encontré con un muy sencillo escrito en VB 6 y después de portarlo a C #, aquí está el resultado: 

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;
}

El código final es tan simple que no creerá que va a funcionar hasta que se ejecute la misma.

Además, el artículo original da una explicación agradable en la forma en que llegó el algoritmo final .

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top