número de diferentes grupos de N enteros que resumen a A

Question

Quiero calcular el número de diferentes grupos ordenados de n números enteros de modo que los elementos de cada grupo resume a A

Por ejemplo: si N = 3 y A = 3 el resultado debería ser 10:
1 = [3, 0, 0]
2 = [2, 1, 0]
3 = [1, 2, 0]
4 = [ 0, 3, 0]
5 = [2, 0, 1]
6 = [1, 1, 1]
7 = [0, 2, 1]
8 = [1, 0, 2]
9 = [0, 1, 2]
10 = [0, 0, 3]

la forma I lo hizo fue por fuerza bruta:

public static int calc(int a, int n){ 
    if (n <= 1 || a == 0) return 1; 

    int sum = 0; 
    for (int i=0; i<=n; i++) 
     sum += calc(a - i, n - 1); 

    return sum; 
} 

sospecho que no puede haber una mejor manera (algunos cálculos matemáticos que falta ..) está ahí?

EDITAR En la pregunta original me olvidó tomar en consideración el orden

Answer 1

Esto es combinatoria composición de A en partes de n (incluyendo el cero partes). El número de composiciones para el par (A, N) es igual a C (A + N - 1, A), donde C() es el número de combinación, también conocido como coeficiente binomial.Consulte la misma fórmula here y here

Answer 2

Estoy seguro de que es un cálculo matemático para responder a esto, pero ya que se trata de una programación Q & A, se lo diré cómo hacer que su programa responda más rápido: puede usar memoization.

Actualmente, su programa vuelve a calcular la respuesta a calc(a, n) todo el tiempo. Sin embargo, la respuesta se puede calcular una vez, porque no cambia en las invocaciones posteriores. Añadir una matriz 2D para el resultado de calc(a,n), inicializar con -1, y lo utilizan para buscar los resultados antes de calcular a ahorrar mucho tiempo en volver a calcular los mismos números una y otra vez:

private static int[][] memo = new int[30][30]; 
static { 
    for(int i = 0 ; i != 30 ; i++) 
     for(int j = 0 ; j != 30 ; j++) 
      memo[i][j] = -1; 
} 
public static int calc(int a, int n){ 
    if (n <= 1 || a == 0) return 1; 
    if (memo[a][n] > 0) return memo[a][n]; 
    int sum = 0; 
    for (int i=0; i<=n; i++) 
     sum += calc(a - i, n - 1); 
    return (memo[a][n] = sum); 
} 

Answer 3

Imagínese segmento grande de longitud A. Y imagine N-1 separadores ordenados, dividiendo el segmento en partes. Por lo tanto, cada parte es un summand, mientras que el segmento entero es una suma.

Ergo, todo lo que necesita es proporcionar un algoritmo para enumerar la ubicación de los separadores.

primer separador que puede poner en cualquiera de las posiciones N+1 P_0 = {0,1, ... N}

segundo separador puede entrar en cualquiera de P_1 = {P_0, ... N}

Y así sucesivamente.

Puede usar recursion para implementar esto.

Answer 4

he encontrado otra solución, sólo con la recursión y sin separadores:

public class App201210121604 { 

public static Vector<int[]> split(int sum, int count) { 

    if(sum < 0) { 
     throw new IllegalArgumentException("Negative sum is not allowed"); 
    } 

    Vector<int[]> ans = new Vector<int[]>(); 

    // "reserved" end of recursion 
    if(count <= 0) { 
     // nothing to do 
    } 

    // end of recursion 
    else if(count == 1) { 
     ans.add(new int[] {sum}); 
    } 

    // body of recursion 
    else { 
     // for each first summand from 0 to summ 
     for(int i=0; i<=sum; ++i) { 

      // do a recursion to get the "tail" 
      for(int[] tail : split(sum-i, count-1)) { 

       int[] group = new int[count]; 
       group[0] = i; 
       System.arraycopy(tail, 0, group, 1, count-1); 

       ans.add(group); 
      } 
     } 
    } 

    return ans; 
} 

public static void main(String[] args) { 

    Vector<int[]> ans = split(8, 4); 

    for(int[] group : ans) { 
     for(int i=0; i<group.length; ++i) { 
      if(i>0) System.out.print("+"); 
      System.out.print(group[i]); 
     } 
     System.out.println(""); 
    } 
} 

} 

Answer 5

Para la enumeración: utilice la fórmula dada en otras soluciones anteriores, MUCHO MÁS EFICIENTE. Nunca querrá generar un conjunto completo de composiciones n-enteras a menos que sea necesario. Contienen propiedades insolubles, especialmente si solo desea totalizarlas, no generarlas. Generarlos es otro problema ...

Generación: utilice un algoritmo sin bucle ... Hay numerosos resultados de secuencia de código O (1) -per gris. Existen muy pocas variaciones de composiciones enteras restringidas que no tienen o pueden tener algoritmos sin bucle. Muchos algoritmos en esta clase de problemas para composiciones enteras, la mayoría de los cuales son muy específicos, pero existen muchos algoritmos modernos sin bucle que existen para este problema específico. Súper eficiente. La fuerza bruta nunca es el camino a seguir con este problema a menos que tenga mucha informática paralela a su disposición. ¡Google o Google Scholar están a tu disposición! : D

Espero que esto ayude!