Iterieren über alle Kombinationen



  • Nabend,

    ich habe hier ein Array aus N Punkten, und ich möchte jetzt alle Kombinationen bekommen, wie ich daraus K Stück auswählen kann. Also die Reihenfolge spielt keine Rolle ("Kombinationen ohne Zurücklegen").
    Kennt hier jemand ein gutes Verfahren, wie ich geschickt über die Kombinationen iterieren kann, ohne viel Zeit zu verschwenden?

    Ich bin schon auf folgende Idee gekommen: einen Zähler hochzählen und in seine Bits zerlegen. Die 1-Bits zählen, und wenn es genau K Stück sind, dann nehme ich mir genau die Punkte raus, bei deren Index eine 1 steht.
    Natürlich führt längst nicht jeder Durchlauf dieses Zählers zu einer gültigen K-Kombination ...

    Es geht doch bestimmt besser, oder?


  • Mod

    Beispiel für systematisch 3 aus 6, lass dich davon mal inspirieren:

    +++...
    ++.+..
    ++..+.
    ++...+
    +.++..
    +.+.+.
    +.+..+
    +..++.
    +..+.+
    +...++
    .+++..
    .++.+.
    .++..+
    .+.++.
    .+.+.+
    .+..++
    ..+++.
    ..++.+
    ..+.++
    ...+++
    

    Umzusetzen beispielsweise mittels Rekursion.




Anmelden zum Antworten