probabilidad - permutaciones y combinaciones

¿Cuál es mejor manera de calcular nCr

Question

Enfoque 1:
C (n, r) = n! / (Nr)! R!

Enfoque 2:
En el libro Combinatorial Algorithms by wilf , he encontrado esto:
C (n, r) se puede escribir como C(n-1,r) + C(n-1,r-1) .

p.ej

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

Como puede ver, la solución final no necesita ninguna multiplicación. En cada forma C (n, r), n == r o r == 1.

Aquí está el código de ejemplo que he implementado:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

Ver output aquí.

En el enfoque 2, hay subproblemas superpuestos en los que llamamos recursión para resolver los mismos subproblemas nuevamente. Podemos evitarlo utilizando la Programación Dinámica .

Quiero saber cuál es la mejor manera de calcular C (n, r).

Answer 1

Ambos enfoques ahorrarán tiempo, pero el primero es muy propenso al desbordamiento de enteros .

Enfoque 1:

Este enfoque generará resultados en el tiempo más corto (en un máximo de n/2 iteraciones), y la posibilidad de desbordamiento se puede reducir haciendo las multiplicaciones con cuidado:

long long C(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

Este código comenzará la multiplicación del numerador desde el extremo más pequeño, y como el producto de cualquier k entero consecutivo es divisible por k! , no habrá problema de divisibilidad. Pero la posibilidad de desbordamiento todavía está allí, otro truco útil puede ser dividir n - r + i y i por su GCD antes de hacer la multiplicación y la división (y aún puede ocurrir un desbordamiento).

Enfoque 2:

En este enfoque, en realidad estarás construyendo el Triángulo de Pascal . El enfoque dinámico es mucho más rápido que el recursivo (el primero es O(n^2) mientras que el otro es exponencial). Sin embargo, también deberá utilizar la memoria O(n^2) .

# define MAX 100 // assuming we need first 100 rows
long long triangle[MAX + 1][MAX + 1];

void makeTriangle() {
    int i, j;

    // initialize the first row
    triangle[0][0] = 1; // C(0, 0) = 1

    for(i = 1; i < MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j <= i; j++) {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
}

long long C(int n, int r) {
    return triangle[n][r];
}

Luego puede buscar cualquier C(n, r) en O(1) tiempo.

Si necesita un C(n, r) (es decir, no se necesita el triángulo completo), entonces el consumo de memoria se puede hacer O(n) sobrescribiendo la misma fila del triángulo, de arriba a abajo.

# define MAX 100
long long row[MAX + 1]; // initialized with 0''s by default if declared globally

int C(int n, int r) {
    int i, j;

    // initialize by the first row
    row[0] = 1; // this is the value of C(0, 0)

    for(i = 1; i <= n; i++) {
        for(j = i; j > 0; j--) {
             // from the recurrence C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
             row[j] += row[j - 1];
        }
    }

    return row[r];
}

El bucle interno se inicia desde el final para simplificar los cálculos. Si lo inicia desde el índice 0, necesitará otra variable para almacenar el valor que se sobrescribe.

Answer 2

Creo que su enfoque recursivo debería funcionar de manera eficiente con DP . Pero comenzará a dar problemas una vez que aumenten las restricciones. Ver http://www.spoj.pl/problems/MARBLES/

Aquí está la función que utilizo en jueces en línea y concursos de codificación. Así que funciona bastante rápido.

long combi(int n,int k)
{
    long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

Es una implementación eficiente para su Enfoque # 1

Answer 3

Su Enfoque Recursivo está bien, pero usar DP con su enfoque reducirá la sobrecarga de resolver los subproblemas nuevamente. Ahora, ya tenemos dos Condiciones:

nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r);

nCr(n,0)=nCr(n,n)=1;

Ahora podemos construir fácilmente una solución de DP almacenando nuestros subresultados en una matriz bidimensional.

int dp[max][max];
//Initialise array elements with zero
int nCr(int n, int r)
{
       if(n==r) return dp[n][r] = 1; //Base Case
       if(r==0) return dp[n][r] = 1; //Base Case
       if(r==1) return dp[n][r] = n;
       if(dp[n][r]) return dp[n][r]; // Using Subproblem Result
       return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

Ahora, si desea obtener más ventajas, obtener la factorización principal del coeficiente binomial es probablemente la forma más eficiente de calcularlo, especialmente si la multiplicación es costosa.

El método más rápido que conozco es el método de Vladimir . Uno evita la división por completo al descomponer el nCr en factores primos. Como dice Vladimir, puede hacer esto de manera bastante eficiente utilizando el tamiz de Eratóstenes. También, use el pequeño teorema de Fermat para calcular la MOD nCr MOD (donde MOD es un número primo).

Answer 4

unsigned long long ans = 1,a=1,b=1;
        int k = r,i=0;
        if (r > (n-r))
            k = n-r;
        for (i = n ; k >=1 ; k--,i--)
        {
            a *= i;
            b *= k;
            if (a%b == 0)
            {
                a = (a/b);
                b=1;
            }
        }
        ans = a/b;