Alle möglichen Kombinationen von n Elementen, die zufällig aus einer Menge von x Elementen ausgewählt werden (Algorithmus)

Question

Ich habe eine Menge von x Zeichenfolgen, z. B. ("A", "B", "C", "D", "E", "F") Ich muss die Formel kennen, die berechnet, wie viele Kombinationen von n Elementen möglich sind, und wie lautet der Algorithmus, der alle möglichen Kombinationen erzeugt z.B. wenn wir 4 Elemente aus der Liste zufällig auswählen müssen. Diese 4 Elemente könnten sein: ("A", "B", "C", "D") oder ("A", "B", "C", "E") oder ("A", "B", "C", "F") oder ("A", "B", "D", "E") ...usw. Ich benötige die Formel, die berechnet, wie viele Mengen von Elementen ohne Wiederholung erzeugt werden, d.h. wenn wir ("A", "B", "C", "D") als eine der resultierenden Kombinationen betrachten, können wir nicht dieselben Elemente als eine andere resultierende Kombination betrachten, indem wir die Positionen der Elemente in der Menge wie ("A", "B", "D", "C") ersetzen. Außerdem benötige ich den Algorithmus, der alle möglichen Kombinationen in einer beliebigen Programmiersprache erzeugt. [C#,VB.NET,Java,C++]

Ich danke Ihnen für jede Hilfe.

Answer 1

Sie können die Anzahl der Kombinationen berechnen, indem Sie Pascalsches Dreieck . Um die tatsächlichen Kombinationen zu finden, können Sie eine einfache Rekursion verwenden.

Answer 2

Ja, das Pascalsche Dreieck funktioniert.

int dp[MAX_X][MAX_Y] = {0};

dp[0][0] = 1;
for (int i = 1; i <= X; i++) {
    dp[i][0] = dp[i][i] = 0;
    for (int j = 1; j < min(i, Y + 1); j++)
        dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
}

print(dp[X][Y])

Alternativ können Sie auch den Schiebefenstertrick anwenden.

Andererseits denke ich, dass die Formel besser funktioniert, solange die Werte nicht zu groß werden.