Numero di combinazioni possibili

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

  •  09-06-2019
  •  | 
  •  

Domanda

Quante combinazioni possibili delle variabili a,b,c,d,e sono possibili se so che:

a+b+c+d+e = 500

e che sono tutti numeri interi e >= 0, quindi so che sono finiti.

È stato utile?

Soluzione

@Torlack, @Jason Cohen:La ricorsione è una cattiva idea qui, perché ci sono "sottoproblemi sovrapposti". Cioè, se lo scegli a COME 1 E b COME 2, ti restano 3 variabili la cui somma dovrebbe dare come risultato 497;si arriva allo stesso sottoproblema scegliendo a COME 2 E b COME 1.(Il numero di tali coincidenze aumenta man mano che i numeri crescono.)

Il modo tradizionale per affrontare un problema del genere è programmazione dinamica:costruire una tabella dal basso verso l'alto delle soluzioni ai sottoproblemi (iniziando con "quante combinazioni di 1 variabile sommano a 0?") quindi costruendo attraverso l'iterazione (la soluzione a "quante combinazioni di N le variabili si sommano a K?" è la somma delle soluzioni di "quante combinazioni di n-1 le variabili si sommano a J?" con 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

Altri suggerimenti

La risposta alla tua domanda è 2656615626.

Ecco il codice che genera la risposta:

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

Nel tuo caso, summands è 5 e sum è 500.

Tieni presente che questo codice è lento.Se hai bisogno di velocità, memorizza nella cache i risultati di summand,sum coppie.

Presumo che tu voglia i numeri >=0.Se vuoi >0, sostituire l'inizializzazione del ciclo con a = 1 e la condizione del ciclo con a < sum.Presumo anche che tu voglia permutazioni (ad es. 1+2+3+4+5 più 2+1+3+4+5 eccetera).Potresti cambiare il ciclo for se lo desideri a >= b >= c >= d >= e.

Ho risolto questo problema per mio padre un paio di mesi fa... estendilo per il tuo uso.Questi tendono ad essere problemi occasionali, quindi non ho scelto quello più riutilizzabile...

a+b+c+d = somma

i = numero di combinazioni

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

Questa sarebbe in realtà una buona domanda da porre durante un colloquio poiché è abbastanza semplice da poter essere scritta su una lavagna, ma abbastanza complessa da poter inciampare qualcuno se non ci pensa abbastanza attentamente.Inoltre, puoi anche avere due risposte diverse che fanno sì che l'implementazione sia abbastanza diversa.

L'ordine è importante
Se l'ordine è importante, qualsiasi soluzione deve consentire la visualizzazione dello zero per qualsiasi variabile;quindi, la soluzione più semplice sarebbe la seguente:

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

Che restituisce 2656615626.

L'ordine non conta
Se l'ordine non ha importanza, la soluzione non è molto più difficile in quanto devi solo assicurarti che lo zero non sia possibile a meno che la somma non sia già stata trovata.

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

Che restituisce 2573155876.

Un modo di considerare il problema è il seguente:

Innanzitutto, a può essere qualsiasi valore compreso tra 0 e 500.Allora se segue che b+c+d+e = 500-a.Ciò riduce il problema di una variabile.Ripetere fino al termine.

Ad esempio, se a è 500, allora b+c+d+e=0, il che significa che nel caso di a = 500 esiste solo una combinazione di valori per b, c, d ed e.

Se a è 300, allora b+c+d+e=200, che in effetti è lo stesso problema originale, solo ridotto di una variabile.

Nota:Come sottolinea Chris, questo è un modo orribile di cercare di risolvere effettivamente il problema.

testo del collegamento

Se sono numeri reali allora infiniti...altrimenti è un po' più complicato.

(OK, per qualsiasi rappresentazione computerizzata di un numero reale ci sarebbe un conteggio finito...ma sarebbe una cosa grossa!)

Ha formule generali, se
a + b + c + d = N
Quindi il numero di soluzioni integrali non negative sarà C(N + number_of_variable - 1, N)

La risposta di @Chris Conway è corretta.Ho provato con un codice semplice adatto a somme più piccole.

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

La risposta in matematica è 504!/(500!*4!).

Formalmente, per x1+x2+...xk=n, il numero di combinazioni del numero non negativo x1,...xk è il coefficiente binomiale:(k-1)-combinazione di un insieme contenente (n+k-1) elementi.

L'intuizione è quella di scegliere (k-1) punti da (n+k-1) punti e utilizzare il numero di punti tra due punti scelti per rappresentare un numero in x1,..xk.

Mi dispiace per la scarsa edizione di matematica per la prima volta che ho risposto a Stack Overflow.

Just a test for code block

Just a test for code block

    Just a test for code block

Inclusi gli aspetti negativi?Infinito.

Includere solo gli aspetti positivi?In questo caso non si chiamerebbero "interi", ma "naturali".In questo caso...Non riesco davvero a risolverlo, vorrei poterlo fare, ma i miei calcoli sono troppo arrugginiti.Probabilmente esiste un modo folle e integrale per risolvere questo problema.Posso dare alcuni suggerimenti per gli esperti di matematica in giro.

Essendo x il risultato finale, l'intervallo di A sarebbe da 0 a x, l'intervallo di b sarebbe da 0 a (x - a), l'intervallo di c sarebbe da 0 a (x - a - b) e così avanti fino all'e.

La risposta è la somma di tutte queste possibilità.

Sto cercando di trovare una formula più diretta su Google, ma oggi sono davvero a corto di Google-Fu...

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top