algorithm - para - Calcular el valor de n elegir k

hashtags exitosos

Question

¿Cuál es el método más eficiente para evaluar el valor de n elige k? Creo que la forma de fuerza bruta sería encontrar n factorial / k factorial / (nk) factorial.

Una mejor estrategia puede ser usar dp de acuerdo con esta fórmula recursiva . ¿Hay algún otro método mejor para evaluar n elegir k?

Answer 1

"Más eficiente" es una solicitud pobre. ¿Qué estás tratando de hacer eficiente? ¿La pila? ¿Memoria? ¿Velocidad? En general, mi opinión es que el método recursivo es más eficiente porque solo usa la suma (una operación barata) y la recursión no será tan mala para la mayoría de los casos. La función es:

nchoosek(n, k)
{
    if(k==0) return 1;
    if(n==0) return 0;
    return nchoosek(n-1, k-1)+nchoosek(n-1,k);
}

Answer 2

Aquí está mi versión, que funciona puramente en enteros (la división por k siempre produce un cociente entero) y es rápida en O (k):

function choose(n, k)
    if k == 0 return 1
    return (n * choose(n - 1, k - 1)) / k

Lo escribí de forma recursiva porque es muy simple y bonito, pero podría transformarlo en una solución iterativa si lo desea.

Answer 3

El problema con n!/k!(nk)! El enfoque no es tanto el costo como el problema con ! creciendo muy rápidamente de modo que, incluso para los valores de nCk que están dentro del alcance de, digamos, los enteros de 64 bits, los cálculos intermedios no lo son. Si no te gusta el enfoque de adición recursiva de kainaw, puedes probar el método multiplicativo:

nCk == product(i=1..k) (n-(ki))/i

donde product(i=1..k) significa el producto de todos los términos cuando tomo los valores 1,2,...,k .

Answer 4

La forma más rápida es probablemente usar la fórmula, y no el triángulo de las pascales. Comencemos a no hacer multiplicaciones cuando sabemos que vamos a dividir por el mismo número más adelante. Si k <n / 2, tengamos k = n - k. Sabemos que C (n, k) = C (n, nk) Ahora:

n! / (k! x (n-k)!) = (product of numbers between (k+1) and n) / (n-k)!

Al menos con esta técnica, nunca se divide por un número que solía multiplicar antes. Tienes (nk) multiplicaciones y (nk) divisiones.

Estoy pensando en una manera de evitar todas las divisiones, encontrando GCDs entre los números que tenemos que multiplicar y los que tenemos que dividir. Intentaré editar más tarde.

Answer 5

Probablemente la forma más fácil de calcular los coeficientes binomiales (n choose k) sin desbordarse es usar el triángulo de Pascal. No se necesitan fracciones ni multiplicaciones. (n choose k) . La fila nth y la entrada kth del triángulo de Pascal dan el valor.

Echa un vistazo a esta página . Esta es una operación O(n^2) con solo suma, que puede resolver con programación dinámica. Va a ser muy rápido para cualquier número que pueda caber en un entero de 64 bits.

Answer 6

Puede usar la fórmula Multiplicativa para esto:

http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

Answer 7

Si tiene una tabla de consulta de factoriales, el cálculo de C (n, k) será muy rápido.

Answer 8

Si vas a calcular muchas combinaciones como esta, calcular el Triángulo de Pascal es la mejor opción. Como ya sabes la fórmula recursiva, creo que puedo pasar un poco de código aquí:

MAX_N = 100
MAX_K = 100

C = [[1] + [0]*MAX_K for i in range(MAX_N+1)]

for i in range(1, MAX_N+1):
    for j in range(1, MAX_K+1):
        C[i][j] = C[i-1][j-1] + C[i-1][j];

print C[10][2]
print C[10][8]
print C[10][3]