Algorithmus für: Alle Möglichkeiten, eine Menge von Elementen in zwei Mengen aufzuteilen?

Question

Ich habe n Elemente in einer Menge U (wir nehmen an, dass sie durch ein Array der Größe n dargestellt wird). Ich möchte alle möglichen Wege finden, die Menge U in zwei Mengen A und B zu unterteilen, wobei |A| + |B| = n.

Wenn also zum Beispiel U = {a,b,c,d}, wären die Kombinationen:

1. A = {a} -- B = {b,c,d}
2. A = {b} -- B = {a,c,d}
3. A = {c} -- B = {a,b,d}
4. A = {d} -- B = {a,b,c}
5. A = {a,b} -- B = {c,d}
6. A = {a,c} -- B = {b,d}
7. A = {a,d} -- B = {b,c}

Beachten Sie, dass die beiden folgenden Fälle als gleichwertig betrachtet werden und nur einer berechnet werden sollte:

Fall 1: A = {a,b} -- B = {c,d}

Fall 2: A = {c,d} -- B = {a,b}

Beachten Sie auch, dass keine der Mengen A oder B leer sein kann.

Die Art und Weise, die ich denke, es zu implementieren ist, indem nur verfolgen Indizes in das Array und verschieben Sie Schritt für Schritt. Die Anzahl der Indizes wird gleich der Anzahl der Elemente in der Menge A sein, und die Menge B wird alle verbleibenden nicht indizierten Elemente enthalten.

Ich habe mich gefragt, ob jemand eine bessere Implementierung kennt. Im suchen für eine bessere Effizienz, weil dieser Code auf eine ziemlich große Menge an Daten ausgeführt werden.

Merci !

Answer 1

Nimm alle ganzen Zahlen von 1 bis 2^(n-1), nicht eingeschlossen. Wenn also n = 4, die ganzen Zahlen von 1 bis 7.

Jede dieser binär geschriebenen Zahlen steht für die Elemente der Menge A. Die Menge B besteht aus den übrigen Elementen. Da wir nur bis 2^(n-1) und nicht bis 2^n gehen, ist das hohe Bit für Menge B immer gesetzt; wir setzen immer das erste Element in Menge B, da die Reihenfolge keine Rolle spielen soll.