Alle möglichen Kombinationen

[kombikuhl]

Wie kann ich mir alle möglichen Kombinationen der Zahlen 1 bis 9 ausgeben lassen? Jede Zahl darf nur einmal vorkommen, muss aber nicht!

Beispiel:
1
1 - 2
1 - 2 - 3
1 - 2 - 3 - 4
1 - 2 - 3 - 4 - 5
1 - 2 - 3 - 4 - 5 - 6
1 - 2 - 3 - 4 - 5 - 6 - 7
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9

Dieses Beispiel zeigt jetzt nur 9 Kombinationen. Wie komme ich jetzt auf Kombinationen wie 1 - 3? Die Reihenfolge ist übrigens auch egal, ob 2 - 1 oder 1 - 2 macht keinen Unterschied!

[Meep Meep]

http://www.cplusplus.com/reference/algorithm/next_permutation/

[kombikuhl]

Diese Funktion kenne ich schon und habe damit auch schon ein wenig rum probiert, mein Problem liegt darin das ich alle Kombinationen brauch. Wenn ich 3 Zahlen angebe, sollen auch alle Kombinationen von nur zwei der drei Zahlen ausgegeben werden.

[Meep Meep]

ach ja. war eigendlich fuer sehende aus deinem beispiel ersichtlich

[Meep Meep]

vielleicht nicht optimal, aber lass einfach die permutation fuer alles x mal durchlaufen wenn du x elemente hast und lass in der schleife (auto i = 1; i <= x ++i) immer nur die ersten i elemente anzeigen.

Meep Meep

[hotcombo]

Was hältst du davon:
- Int von 1 bis 2^9 hochzählen
- Wenn das i-te Bit gesetzt ist, i in einen vektor einfügen
- next_permutation auf den Vektor aufrufen

Die andere Möglichkeit wäre
- Alle 10^9 Kombinationen generieren (0 steht für leer)
- Alle invaliden rausfiltern (0er dürfen nur am Anfang stehen, jede Zahl nur einmal vorkommen)
- Die restlichen ausgeben.

Ist halt beides total lahm (wobei das 2. noch lahmer als das 1. ist), wird eine Zeit dauern, das alles auszugeben.

[seldon]

Wenn die Reihenfolge egal ist, sind das ja nur 512 Kombinationen. Hotcombo hat im Grunde die Lösung schon genannt: von 0 bis 512 hochzählen, und wenn das nte Bit gesetzt ist, ist es als Teil der Kombination zu verstehen.

#include <iostream>

int main() {
  for(int i = 0; i < (1 << 9); ++i) {
    for(int j = 0; j < 9; ++j) {
      if(i >> j & 1) {
        std::cout << j + 1 << ", ";
      }
    }
    std::cout << '\n';
  }
}

Der next_permutation-Teil wäre nur notwendig, wenn 1-2 und 2-1 unterschiedlich behandelt werden müssten.