Número de combinações possíveis

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

  •  09-06-2019
  •  | 
  •  

Pergunta

Quantas combinações possíveis das variáveis ​​a,b,c,d,e são possíveis se eu souber que:

a+b+c+d+e = 500

e que são todos inteiros e >= 0, então sei que são finitos.

Foi útil?

Solução

@Torlack, @Jason Cohen:A recursão é uma má idéia aqui, porque existem "subproblemas sobrepostos". Ou seja, se você escolher a como 1 e b como 2, então você tem 3 variáveis ​​restantes que devem somar 497;você chega ao mesmo subproblema escolhendo a como 2 e b como 1.(O número dessas coincidências explode à medida que os números crescem.)

A maneira tradicional de atacar tal problema é programaçao dinamica:construir uma tabela de baixo para cima das soluções para os subproblemas (começando com "quantas combinações de 1 variável somam 0?") e depois construir através da iteração (a solução para "quantas combinações de n variáveis ​​somam k?" é a soma das soluções para "quantas combinações de n-1 variáveis ​​somam j?" com 0 <= j <= k). 

public static long getCombos( int n, int sum ) {
  // tab[i][j] is how many combinations of (i+1) vars add up to j
  long[][] tab = new long[n][sum+1];
  // # of combos of 1 var for any sum is 1
  for( int j=0; j < tab[0].length; ++j ) {
    tab[0][j] = 1;
  }
  for( int i=1; i < tab.length; ++i ) {
    for( int j=0; j < tab[i].length; ++j ) {
      // # combos of (i+1) vars adding up to j is the sum of the #
      // of combos of i vars adding up to k, for all 0 <= k <= j
      // (choosing i vars forces the choice of the (i+1)st).
      tab[i][j] = 0;
      for( int k=0; k <= j; ++k ) {
        tab[i][j] += tab[i-1][k];
      }
    }
  }
  return tab[n-1][sum];
}

$ time java Combos
2656615626

real    0m0.151s
user    0m0.120s
sys 0m0.012s

Outras dicas

A resposta à sua pergunta é 2656615626.

Aqui está o código que gera a resposta:

public static long getNumCombinations( int summands, int sum )
{
    if ( summands <= 1 )
        return 1;
    long combos = 0;
    for ( int a = 0 ; a <= sum ; a++ )
        combos += getNumCombinations( summands-1, sum-a );
    return combos;
}

No seu caso, summands é 5 e sum é 500.

Observe que este código é lento.Se você precisar de velocidade, armazene em cache os resultados de summand,sum pares.

Presumo que você queira números >=0.Se você quiser >0, substitua a inicialização do loop por a = 1 e a condição de loop com a < sum.Também estou assumindo que você deseja permutações (por exemplo, 1+2+3+4+5 mais 2+1+3+4+5 etc).Você poderia alterar o loop for se quisesse a >= b >= c >= d >= e.

Resolvi esse problema para meu pai há alguns meses... estenda para seu uso.Esses tendem a ser problemas únicos, então não optei pelo mais reutilizável ...

a+b+c+d = soma

i = número de combinações

        for (a=0;a<=sum;a++)
        {
            for (b = 0; b <= (sum - a); b++)
            {
                for (c = 0; c <= (sum - a - b); c++)
                {
                    //d = sum - a - b - c;
                    i++
                }
            }
        }

Na verdade, essa seria uma boa pergunta para fazer em uma entrevista, pois é simples o suficiente para ser escrita em um quadro branco, mas complexa o suficiente para que alguém possa enganar alguém se não pensar com cuidado suficiente sobre isso.Além disso, você também pode obter duas respostas diferentes que fazem com que a implementação seja bem diferente.

Pedidos são importantes
Se a ordem for importante, então qualquer solução precisa permitir que zero apareça para qualquer uma das variáveis;assim, a solução mais direta seria a seguinte:

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 0; a <= 500; a++) {
            for (int b = 0; b <= (500 - a); b++) {
                for (int c = 0; c <= (500 - a - b); c++) {
                    for (int d = 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

O que retorna 2656615626.

A ordem não importa
Se a ordem não importa, a solução não é muito mais difícil, pois você só precisa ter certeza de que zero não é possível, a menos que a soma já tenha sido encontrada.

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 1; a <= 500; a++) {
            for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
                for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
                    for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

Que retorna 2573155876.

Uma maneira de ver o problema é a seguinte:

Primeiro, a pode ter qualquer valor de 0 a 500.Então se segue que b+c+d+e = 500-a.Isso reduz o problema em uma variável.Recorra até terminar.

Por exemplo, se a for 500, então b+c+d+e=0, o que significa que para o caso de a = 500, existe apenas uma combinação de valores para b,c,d e e.

Se a for 300, então b+c+d+e=200, que é na verdade o mesmo problema do problema original, apenas reduzido em uma variável.

Observação:Como Chris aponta, esta é uma maneira horrível de realmente tentar resolver o problema.

Texto do link

Se forem números reais então infinitos...caso contrário, é um pouco mais complicado.

(OK, para qualquer representação computacional de um número real haveria uma contagem finita...mas seria grande!)

Tem fórmulas gerais, se
a + b + c + d = N
Então o número de soluções integrais não negativas será C(N + number_of_variable - 1, N)

A resposta do @Chris Conway está correta.Testei com um código simples que é adequado para quantias menores.

                    long counter = 0;
            int sum=25;

            for (int a = 0; a <= sum; a++) {
                for (int b = 0; b <= sum ; b++) {
                    for (int c = 0; c <= sum; c++) {
                        for (int d = 0; d <= sum; d++) {
                             for (int e = 0; e <= sum; e++) {
                           if ((a+b+c+d+e)==sum) counter=counter+1L;

                             }
                       }
                    }
                }
            }
            System.out.println("counter e "+counter);

A resposta em matemática é 504!/(500!*4!).

Formalmente, para x1+x2+...xk=n, o número de combinação do número não negativo x1,...xk é o coeficiente binomial:(k-1)-combinação de um conjunto contendo (n+k-1) elementos.

A intuição é escolher (k-1) pontos de (n+k-1) pontos e usar o número de pontos entre dois pontos escolhidos para representar um número em x1,..xk.

Desculpe pela má edição de matemática pela primeira vez respondendo ao Stack Overflow.

Just a test for code block

Just a test for code block

    Just a test for code block

Incluindo negativos?Infinito.

Incluindo apenas pontos positivos?Neste caso eles não seriam chamados de "inteiros", mas sim de "naturais".Nesse caso...Eu realmente não consigo resolver isso, gostaria de poder, mas minha matemática está muito enferrujada.Provavelmente existe alguma maneira integral e maluca de resolver isso.Posso dar algumas dicas para os especialistas em matemática.

Sendo x o resultado final, o intervalo de a seria de 0 a x, o intervalo de B seria de 0 a (x - a), o intervalo de C seria de 0 a (x - a - b) e assim até o e.

A resposta é a soma de todas essas possibilidades.

Estou tentando encontrar alguma fórmula mais direta no Google, mas estou com muito pouco Google-Fu hoje...

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top