Kombinatorik - Mathematik

It0101

Hi Leute

ich steh grad ein bisschen auf dem Schlauch.

Ich habe eine Menge von N Objekten.
Daraus will ich alle verschiedenen Kombinationen von M ( fuer M < N ) Objekten ermitteln. Keine Dopplungen.

Also quasi fuer N = 4 und M = 3:

Ausgangsmenge:
1 2 3 4

Kombinationen:
1 2 3
2 3 4
1 3 4

Ich bin mir noch nicht sicher, wie ich das umsetzen kann.
Erste Möglichkeit ist, alles mit allem zu kombinieren und die überflüssigen rauszuwerfen. Das ist genau die Lösung, die ich nicht will!

Jemand eine bessere Idee?

volkard

Ausgangsmenge:
1 2 3 4

Kombinationen:
1 2 3
1 2 4
1 3 4
2 3 4

Formel: http://de.wikipedia.org/wiki/Binomialkoeffizient

Bashar

Das geht am einfachsten rekursiv. Du willst aus einer Menge A mit n Elementen alle Untermengen mit m Elementen auswählen. Dazu betrachtest du alle a in A und bildest jeweils die Menge A' aller Elemente aus A, die größer als a sind. Aus A' wählst du dann (Rekursion!) m-1 Elemente aus.

Die Auswahl von 3 Elementen aus 1234 liefe beispielsweise so, dass du
* 1 plus alle 2-Teilmengen von 234
* 2 plus alle 2-Teilmengen von 34
* 3 plus alle 2-Teilmengen von 4 (es gibt keine, aber egal)
bildest, also der Reihenfolge nach 123, 124, 134, 234.

Brauchst du eine Implementation? In welcher Form sollen die Ergebnisse ausgegeben werden? Welche Programmiersprache?

It0101

Du hast recht, ich hab sogar noch eine Variation vergessen ^^

Der Binomialkoeffizient gibt ja nur die Anzahl der Varianten an... Das bringt mir nix.

It0101

An eine rekursive Version hatte ich auch schon gedacht...

Sprache wäre C/C++. Textausgabe wäre ausreichend. In Strukturen würde ich die jeweilige Variation dann schon selber verfrachten

Ich denke erstmal weiter über die rekursive Version nach

Die Idee mit der Rekursion reicht mir erstmal. Ich bastel mal ne Runde.

It0101

Die Lösung hier ist iterativ:

int MaxSize = 5; // Alle verfuegbaren Zahlen
int Size = 3; // Groesse der Varianten

int *A = new int[ Size ];
// Setzen die erste Variante
for ( int i = 0; i < Size; ++i )
    A[i] = i;

int x = Size - 1; // Die aktuelle Position - beginnt auf der letztmoeglichen Position
bool bQuit = false;
while ( !bQuit )    
{
    // Pruefen ob jede weitere Ziffer groesser ist als ihr Vorgaenger
    bool bOK = true;
    for ( int j = 1; j < Size; ++j )
        bOK = bOK && A[j] > A[j-1];
    if ( bOK )
    {
        // Geben die Zahl aus
        for ( int j = 0; j < Size; ++j )
            std::cout << A[j];
        std::cout << std::endl;
    }

    // Erhoehen die Ziffer an der Stelle x um 1
    A[x]++;
    // Springen solange um eine Spalte nach links, bis eine gueltige Ziffer erreicht wurde
    while ( A[x] >= MaxSize )
    {
        A[x] = 0; // Null setzen ( kleine moegliche Ziffer )
        --x;      // Eine Spalte zurueck 
        if ( x < 0 ) // Wenn wir ganz vorn angekommen sind, sind wir fertig
        {
            bQuit = true;
            break;
        }
        ++A[x];   // Eins erhoehen
    }
    x = Size - 1; // Setzen den Cursor wieder nach hinten
}
delete [] A;

Kurze Beschreibung:

3 aus 4 ( 0 1 2 3 )

Ich nehme die (kleinste) erste moegliche Variation ( 0 1 2 ).
Erhöhe die letzte Ziffer.
Ist die Ziffer zu groß ( > 3 ), setze ich sie 0.
Ich springe jetzt solange zurück bis ich durch Erhöhung eine gültige Zahl erreiche. ( Alle Zahlen dahinter sind jetzt 0 ).
Nun erhöhe ich wiederum die letzte Ziffer.
usw.