n über k möglichkeiten von elementen eines arrays berechnen

wxSkip

Ich glaube, er will nicht den Binomialkoeffizienten berechnen, sondern die Kombinationen ausgeben. Da würde ich es spontan mit einem rekursiven Ansatz versuchen (d.h. vom verbleibenden Array einmal die nächste Zahl auswählen und einmal nicht und dann die Funktion rekursiv auf das verbleibende Array ohne die ausgewählte Zahl aufrufen).

philipp2100

Ah ja. Das würde so gehen, aber du müsstest natürlich dieser Funktion noch übergeben, wieviele Zahlen du bereits hast und die Rekursion ggfs. abbrechen.
Außerdem musst du darauf achten, die Zahlen immer schön paarweise zu haben, denn die Rekursion verarbeitet bspw. die 1. Zahl niemals doppelt: Wenn sie ausgewählt wird, dann einmal und dann wird in der nächsten Rekursionsebene die nächste Zahl ausgewählt, wenn k = 2 ist dann im selben Aufruf noch eine usw.. D.h. für k = 2 und n = 3 kriegst du 1 2 3 2 3 für (1, 2) (1, 3) (2, 3) - die 1 kommt nicht doppelt vor. Das vermeiden und auch gleichzeitig dafür sorgen, dass nicht bspw. die 3 dann nochmal alleine verarbeitet wird kannst du mit den Standard-Containern: du nimmst dir einen std::vector, den alle Funktionsinstanzen sehen können, pushst da immer die Zahl rein, die du auswählen willst und wenn er die Größe k hat, gibst du ihn an eine andere Funktion, die ihn verarbeitet - und dann popst du die Zahl wieder.

Ich hätte noch eine andere, iterative Lösung, die aber nur für n < 64 funktioniert (edit) und die vor allem Sinn macht, wenn du auch große k's hast (und bei der ich auf Kommentare gespannt wäre): du betrachtest die Zahl 2^n (2 hoch n) als Bitfeld und schreibst eine Schleife von 0 bis 2^n - 1 (edit), in der du jede Zahl i verarbeitest, in der in der Binärdarstellung von i genau k 1en vorkommen; die Position der 1en zeigt dir die Indizes der Zahlen an, bspw. stünde für n = 3 der Wert 001 = 1 für "es wird nur das erste Element ausgewählt" (denn die 1 steht an der ersten Stelle). Implementieren könnte man das so:

if (k == 0) return 0;
/* we start with the combination 2^k - 1 */
unsigned long long start = 0;
for (int e = 0; e < k; ++e) {
    start += powl(2, e);
}
for (unsigned long long comb = start; comb < powl(2, n); ++comb) {
    int ones = 0;  // number of ones in combination
    for (unsigned long long i = comb; i > 0; i /= 2) {
        if (i % 2 == 1) {  // we have a one as the lowest digit
            if (++ones == k) {  // count it; do we have enough?
                process(comb);
                i = comb;  //// skip useless combinations:
                int pos = 0;
                while (1) {  // set bits <= first one-bit to zero 
                    if (i % 2 == 1) {
                        comb -= powl(2, pos);
                        break;
                    }
                    i /= 2;
                    ++pos;
                }
                comb += powl(2, pos + 1);  // set bit one higher than first one to one
                comb -= 1;  // subtract 1, will be added again by for-loop over combinations
                break;  // "for (unsigned long long i = comb; i > 0; i /= 2)"
            }  // "if (++ones == k)"
        }  // "if (i % 2 == 1)"
    }
}

Werde gleich mal selber probieren ob der Code geht..
edit: Typ von comb in unsigned long long geändert. while korrekterweise durch for ersetzt. break hinzugefügt. Tippfehler korrigiert (shift -> shifts). Schließende Klammer hinzugefügt (vorletzte Zeile). i /= 2 in Schleifenkopf verlagert und falsches ++i gelöscht. Typ von i in unsigned long long geändert. Sonderfall k = 0 berücksichtigt (erste Zeile). pow überall durch powl ersetzt. Überflüssige Variable shifts eliminiert. Starten bei 2^k - 1 anstatt bei 0.

edit: Ok, ein logischer Fehler war noch drin. Er sprang zu weit und kriegte so nicht alle Kombinationen. Man darf nicht alle Einsen die man gelesen hat auf Null setzen und dann das nächsthöhere Bit auf Eins, sondern dieses nur bis zur ersten Eins. Daher habe ich aus der for-Schleife mit for (int pos = 0; pos <= shifts; ++pos) noch eine entsprechende while-Schleife gemacht.

Hier mal ein vollständiges Testprogramm, btw., könnte mir einer erklären warum die Benutzung der pow() -Funktion bei Kompilation als C-Programm einen Linker-Error gibt:

#include <stdio.h>
#include <math.h>

int n = 5;
int k = 2;

void process(unsigned long long comb) {
    int numbers[k];
    int number = 0;
    int pos = 1;  // 1-based
    for (unsigned long long i = comb; i > 0; i /= 2, ++pos) {
        if (i % 2 == 0) continue;
        if (number < k) numbers[number++] = pos;
        else printf("Something went wrong: #numbers > k!");
    }
    printf("Decimal: %llu -> ", comb);
    for (int i = 0; i < k; ++i) {
        printf("%d%s", numbers[i], i < k - 1 ? " " : "");
    }
    putchar('\n');
}

int main() {
    if (k == 0) return 0;
    /* we start with the combination 2^k - 1 */
    unsigned long long start = 0;
    for (int e = 0; e < k; ++e) {
        start += powl(2, e);
    }
    for (unsigned long long comb = start; comb < powl(2, n); ++comb) {
         int ones = 0;  // number of ones in combination
         for (unsigned long long i = comb; i > 0; i /= 2) {
             if (i % 2 == 1) {  // we have a one as the lowest digit 
                 if (++ones == k) {  // count it; do we have enough? 
                     process(comb);
                     i = comb;  //// skip useless combinations:
                     int pos = 0;
                     while (1) {  // set bits <= first one-bit to zero 
                         if (i % 2 == 1) {
                             comb -= powl(2, pos);
                             break;
                         }
                         i /= 2;
                         ++pos;
                     }
                     comb += powl(2, pos + 1);  // set bit one higher than first one to one
                     comb -= 1;  // subtract 1, will be added again by for-loop over combinations
                     break;  // "for (unsigned long long i = comb; i > 0; i /= 2)"
                 }  // "if (++ones == k)" 
             }  // "if (i % 2 == 1)"
        }
    }
}

philipp2100

Hier nochmal eine Version, die für große k sehr viel schneller ist (ich konnte es nicht lassen ). Darauf aufbauend kann man sich auch leicht eine Version vorstellen, die mit std::vector<bool> arbeitet anstatt mit einer unsigned long long Variable und dann auch für n >= 64 funktioniert.
Dann kann man sich auch die Arithmetik beim Setzen der 0en und 1en sparen.

edit: Tue mal die 3 printf()- bzw. putchar()-Zeilen in der process() -Funktion wieder einkommentieren. Die sollte man bei Performance-Tests natürlich weglassen...
edit: Da der Code jetzt zuverlässig comb auf die nächste gültige Kombination setzt, kann man sich den Test sparen, ob diese wirklich k Einsen enthält. Dahingehend hab ich den Code noch vereinfacht (zwei if-Verzweigungen und eine for-Schleife über jeweils den ganzen Code aus der äußeren for-Schleife fallen weg).

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int n = 14;
int k = 12;
long long combinations_found = 0;

long long binomial(int n, int k) {
    if (k < 0 || n < k) return 0;
    if (k == 0) return 1;
    if (2 * k > n) return binomial(n, n - k);
    long long result = n - k + 1;
    for (int i = 2; i <= k; ++i) {
        result *= n - k + i;
        result /= i;
    }
    return result;
}

void process(unsigned long long comb) {
    ++combinations_found;
    int numbers[k];
    int number = 0;
    int pos = 1;  // 1-based
    for (unsigned long long i = comb; i > 0; i /= 2, ++pos) {
        if (i % 2 == 0) continue;
        if (number < k) numbers[number++] = pos;
        else printf("Something went wrong: combination %llu contains more than k numbers!\n", comb);
    }
    printf("Decimal: %llu -> ", comb);
    for (int i = 0; i < k; ++i) {
        printf("%d%s", numbers[i], i < k - 1 ? " " : "");
    }
    putchar('\n');
}

int main() {
    if (k == 0) return 0;
    /* we start with the combination 2^k - 1 */
    unsigned long long start = 0;
    for (int e = 0; e < k; ++e) {
        start += powl(2, e);
    }
    for (unsigned long long comb = start; comb < powl(2, n); ) {
        process(comb);
        /*
         * Now we set comb to represent the next sensible combination.
         * To do that, we locate the first one-bit followed by a zero-bit and change it
         * to a zero-bit followed by a one-bit.
         * Because we might have jumped over some meaningful combinations by that, we then
         * "pull back" all the one-bits before (lower) the one we created in the first step
         * as fare as possible.
         * E.g. 01100 becomes 10100 in the first step and then 10001 after pulling back the
         * one-bits.
         *
         */
        unsigned long long candidate = comb;
        int pos = 0;  // zero-based position in binary representation of comb
        /* the meaning of last_one is: "Was the digit read on the previous position a one?" */
        for (bool last_one = false; ; candidate /= 2, ++pos) {
            if (candidate % 2 == 1) {
                last_one = true;
            } else {
                if (last_one) break;
            }
        }
        /* pos - 1 is now the zero-based index of the first one followed by a zero,
         * pos the index of that zero  */
        comb -= powl(2, pos - 1);  // set that one-bit to zero
        comb += powl(2, pos);  // set the zero-bit to one
        /* pull back all ones before pos - 1 as far as possible, e.g. 10100 -> 10001 where pos - 1 = 3 */
        candidate = comb;
        for (int i = 0; i < pos - 1; candidate /= 2, ++i) {
            if (candidate % 2 == 0) {
                unsigned long long temp = candidate;
                int j = 0;  // distance to next one-bit
                while (1) {
                    temp = temp / 2;
                    ++j;
                    if (temp % 2 == 1) break;
                    if (i + j == pos - 1) {
                        j = 0;
                        break;
                    }
                }
                comb -= powl(2, i + j);
                comb += powl(2, i);
                candidate -= powl(2, j);  // since candidate is shrinked by the i /-operations, we don't need i here
                candidate += powl(2, 0);  // since candidate is shrinked by the i /-operations, we don't need i here
            } else {
                /* we can break here because a one with a zero after it won't occur -
                 * they would have been recognized above so pos would be smaller */
                break;  // "for (int i = 0; i < pos - 1; candidate /= 2, ++i)"
            }
        }  // "for (int i = 0; i < pos - 1; candidate /= 2, ++i)"
    }  // "for (unsigned long long comb = start; comb < powl(2, n); )"
    printf("Found %lld of %lld possible combinations.\n", combinations_found, binomial(n, k));
}

volkard

philipp2100 schrieb:

Hier nochmal eine Version, die für große k sehr viel schneller ist (ich konnte es nicht lassen )

Wie im Vergleich zu std::next_permutation?

philipp2100

Es geht nicht um Permutationen sondern um kombinatorische Möglichkeiten.

volkard

philipp2100 schrieb:

Es geht nicht um Permutationen sondern um kombinatorische Möglichkeiten.

Uups.
Werde Deinen Code durchdenken.

philipp2100

Das ist nett. Besonders nett wäre es, wenn du mir sagen könntest, warum es, als C-Programm kompiliert, einen undefined reference to 'powl' gibt (also die alte Version)... Das wirklich verrückte daran ist, dass powl(2, 2) funktioniert, mit Variablen hat er aber Probleme..

volkard

philipp2100 schrieb:

Hier mal ein vollständiges Testprogramm, btw., könnte mir einer erklären warum die Benutzung der pow() -Funktion bei Kompilation als C-Programm einen Linker-Error gibt:

#include <stdio.h>
#include <math.h>

int n = 5;
int k = 2;

void process(unsigned long long comb) {
    int numbers[k];
    int number = 0;
    int pos = 1;  // 1-based
    for (unsigned long long i = comb; i > 0; i /= 2, ++pos) {
        if (i % 2 == 0) continue;
        if (number < k) numbers[number++] = pos;
        else printf("Something went wrong: #numbers > k!");
    }
    printf("Decimal: %llu -> ", comb);
    for (int i = 0; i < k; ++i) {
        printf("%d%s", numbers[i], i < k - 1 ? " " : "");
    }
    putchar('\n');
}

int main() {
    if (k == 0) return 0;
    /* we start with the combination 2^k - 1 */
    unsigned long long start = 0;
    for (int e = 0; e < k; ++e) {
        start += powl(2, e);
    }
    for (unsigned long long comb = start; comb < powl(2, n); ++comb) {
         int ones = 0;  // number of ones in combination
         for (unsigned long long i = comb; i > 0; i /= 2) {
             if (i % 2 == 1) {  // we have a one as the lowest digit 
                 if (++ones == k) {  // count it; do we have enough? 
                     process(comb);
                     i = comb;  //// skip useless combinations:
                     int pos = 0;
                     while (1) {  // set bits <= first one-bit to zero 
                         if (i % 2 == 1) {
                             comb -= powl(2, pos);
                             break;
                         }
                         i /= 2;
                         ++pos;
                     }
                     comb += powl(2, pos + 1);  // set bit one higher than first one to one
                     comb -= 1;  // subtract 1, will be added again by for-loop over combinations
                     break;  // "for (unsigned long long i = comb; i > 0; i /= 2)"
                 }  // "if (++ones == k)" 
             }  // "if (i % 2 == 1)"
        }
    }
}

Kein Fehler, geht bei mir auf Anhieb.
edit: Falsch, in C hab ich auch den Fehler.

edit2: -lm muss her, dann gehts.
Zur Laufzeit muss die mathelib reingelinkt werden.
Zur Compilezeit, der Compiler hat sie, während er selber läuft.

SeppJ

philipp2100 schrieb:

Das ist nett. Besonders nett wäre es, wenn du mir sagen könntest, warum es, als C-Programm kompiliert, einen undefined reference to 'powl' gibt (also die alte Version)... Das wirklich verrückte daran ist, dass powl(2, 2) funktioniert, mit Variablen hat er aber Probleme..

Du musst noch gegen die Mathebibliothek linken (Oft mittels Kommandozeilenparameter -lm ). Wenn du konstanten reinschreibst, dann rechnet der Compiler direkt das Ergebnis aus und braucht die Funktion nicht. Ist das Argument variabel, so brauchst du wirklich die Bibliothek mit der Funktion. Die Mathefunktionen sind in C zwar Teil des Standards, aber traditionell als eigenständige Bibliothek organisiert.

philipp2100

SeppJ schrieb:

philipp2100 schrieb:

Das ist nett. Besonders nett wäre es, wenn du mir sagen könntest, warum es, als C-Programm kompiliert, einen undefined reference to 'powl' gibt (also die alte Version)... Das wirklich verrückte daran ist, dass powl(2, 2) funktioniert, mit Variablen hat er aber Probleme..

Du musst noch gegen die Mathebibliothek linken (Oft mittels Kommandozeilenparameter -lm ). Wenn du konstanten reinschreibst, dann rechnet der Compiler direkt das Ergebnis aus und braucht die Funktion nicht. Ist das Argument variabel, so brauchst du wirklich die Bibliothek mit der Funktion. Die Mathefunktionen sind in C zwar Teil des Standards, aber traditionell als eigenständige Bibliothek organisiert.

Aaaah! Besten Dank!