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

Wählt man p aus n Gegenständen aus, so ist dies die Formel, die die Anzahl der Kombinationen angibt.

                  n!
n choose p  = -----------
               p! (n-p)!

Der Google-Rechner übernimmt die Berechnung für Sie:

http://www.google.com/search?q=6+Auswahl+4

6 wählen 4 = 15

Answer 2

Die Formel für a Kombination die Sie beschreiben, finden Sie in der Antwort von @Mark Harrison. Setzen Sie diese Gleichung jedoch ein, und sie wird explodieren, weil die Mathematik sich aufheben soll.

Beispiel: 50 wählt 49 - das ist dasselbe wie die Wahl des auszuschließenden Elements, es gibt also 50 Auswahlmöglichkeiten. Die Formel würde jedoch erfordern, dass Sie Folgendes berechnen

   50!       3.04140932e64
-------- = ----------------- = 50
1! * 49!   1 * 6.08281864e62

Die Gleichung, die Sie "wirklich" für x wählen y wollen, lautet

x * (x-1) * ... * (x-n+1)
-------------------------
n * (n-1) * ... * 2 * 1

Einige einfache C-Codes [beachten Sie, dass dadurch optimiert wird, dass C(x,y) = C(x,x-y) - dies sollte aus der Kombinationsformel leicht zu erkennen sein]:

int c(int x, int y)
{
    int num = 1, denom = 1;
    int i;
    if (y > x-y)
        y = x - y;
    for (i = 0; i < y; ++i)
    {
        num *= (x - i);
        denom *= (y - i);
    }
    return num/denom;
}

Wenn Sie also alle möglichen Buchstabenkombinationen "ABCDEF" suchen, bei denen Sie 4 Buchstaben auswählen, ist das c(6,4) .

Answer 3

Ich brauche den Algorithmus, der alle möglichen Kombinationen in einer beliebigen Programmiersprache erzeugt.

Okay, hier ist eine einzeilige Lösung in Haskell:

import Data.List (subsequences)

n `outOf` xs = filter ((n ==) . length) (subsequences xs)

test = 4 `outOf` ["A", "B", "C", "D", "E", "F"]

*Main> test
[["A","B","C","D"],["A","B","C","E"],["A","B","D","E"],["A","C","D","E"],["B","C
","D","E"],["A","B","C","F"],["A","B","D","F"],["A","C","D","F"],["B","C","D","F
"],["A","B","E","F"],["A","C","E","F"],["B","C","E","F"],["A","D","E","F"],["B",
"D","E","F"],["C","D","E","F"]]
*Main> length test
15

Answer 4

Sie benötigen die Binomischer Lehrsatz und Sie benötigen verschachtelte Schleifen. Eine Implementierung in einer Ihrer Programmiersprachen ist nicht allzu schwierig zu schreiben. Wenn Sie sich umsehen, werden Sie feststellen, dass diese Frage regelmäßig auf SO gestellt wird, und Sie werden Leute finden, die dafür stimmen, Ihre Frage aus diesem Grund zu schließen.

Answer 5

Sie können sich auch für Lexikografische Ordnung .

Etwa so:

#include <stdio.h>

void print(const int *v, const int size)
{
    int i;
    if (v != 0) {
        for (i = 0; i < size; i++) {
            printf("%4d", v[i] );
        }
        printf("\n");
    }
} // print

void visit(int *Value, int N, int k)
{
    int i;
    static level = -1;
    level = level+1; Value[k] = level;

    if (level == N)
        print(Value, N);
    else
        for (i = 0; i < N; i++)
            if (Value[i] == 0)
                visit(Value, N, i);

    level = level-1; Value[k] = 0;
}

main()
{
    const int N = 4;
    int Value[N];
    int i;
    for (i = 0; i < N; i++) {
        Value[i] = 0;
    }
    visit(Value, N, 0);
}