Teilmengen aufzählen
-
Gegeben ist die Menge die aus den Zahlen 1 bis n besteht. Ich brauche einen Algorithmus der mir alle Teilmengen dieser Menge mit der Länge m aufzählt. Alternativ reicht mir auch ein Algorithmus der mir alle Teilmengen mit einer Länge kleiner oder gleich m aufzählt.
Der Algorithmus sollte möglichst effizient sein. Auf die Idee einfach alle Teilmengen aufzuzählen und für jede zu überprüfen ob die Anzahl der Elemente stimmt bin ich schon selbst gekommen, reicht mir aber nicht.
Hat jemand eine Idee?Mir geht es nicht darum die Anzahl der Teilmengen zu bestimmen. Ich will für jede dieser Teilmengen eine Bedingung überprüfen.
-
Welche Bedingung möchtest du prüfen?
-
@Hubert-Alfonsius sagte in Teilmengen aufzählen:
Welche Bedingung möchtest du prüfen?
Ich will eine Mengen (A) von Mengen finden deren Vereinigung genauso viele Elemente hat wie die Menge (A).
-
Also ich würde manuell so rangehen (M sei die (irgendwie) geordnete Menge mit m Elementen)
Ich soll n Elemente wählen.Also kann ich entweder
- das erste Element aus M auswählen und dann n-1 Elemente aus M[1..ende] wählen
- oder das erste Element nicht auswählen und n Elemente aus M[1..ende] wählen
Rekursiv weitermachen. Jetzt noch die Abbruchbedingungen in den Code und fertig.
In C++ könnte man sich alternativ auch eine "Maske" basteln, z.B. einen vector mit {0,...,0,1,...,1} (hinten n Einsen, Gesamtlänge m). Das wäre dann "wähle die hinteren 3 Elemente". Mit std::next_permutation könnte man dann die Maske durchpermutieren.