Wie berechnet man die Gesamtzahl aller möglichen eindeutigen Teilmengen aus einem Satz mit Wiederholungen?

Question

Gegeben eine Menge ** S, die doppelte Elemente enthält, wie kann man die Gesamtzahl aller möglichen Teilmengen von S bestimmen, wobei jede Teilmenge eindeutig ist.

Sagen wir zum Beispiel S = {A, B, B} und sei K die Menge aller Teilmengen, dann K = {{}, {A}, {B}, {A, B}, {B , B}, {A, B, B}} und daher | K | = 6

Ein anderes Beispiel wäre, wenn S = {A, A, B, B}, dann K = {{}, {A}, {B}, {A, B}, {A, A} , {B, B}, {A, B, B}, {A, A, B}, {A, A, B, B}} und dafür | K | = 9

Es ist leicht zu sehen, dass, wenn S eine echte Menge ist, nur einzigartige Elemente haben, dann | K | = 2^| S |.

Was ist eine Formel, um diesen Wert | K | zu berechnen gegeben ein "set" S (mit Duplikaten), ohne alle Teilmengen zu generieren?

** Nicht technisch ein Satz.

Answer 1

Nehmen Sie das Produkt aller (Frequenzen + 1).

beispielsweise in {A, B, B}, ist die Antwort (1 + 1) [die Zahl der A] * (2 + 1) [die Anzahl der Bs] = 6.

In Das zweite Beispiel, count (A) = 2 und count (B) = 2. Die Antwort ist also (2 + 1) * (2 + 1) = 9.

Der Grund dafür ist, dass Sie beliebige definieren können Teilmenge als Vektor von Zählungen - für {A, B, B} können die Teilmengen beschrieben werden als {A = 0, B = 0}, {A = 0, B = 1}, {0,2}, {1 , 0}, {1,1}, {1,2}.

Für jede Zahl in counts [] gibt es (Frequenzen des Objekts + 1) mögliche Werte. (0..frequencies)

Daher ist die Gesamtzahl der Möglichkeiten das Produkt von allen (Häufigkeiten + 1).

Der Fall "all unique" kann auch so erklärt werden - es gibt ein Vorkommen jedes Objekts, also lautet die Antwort (1 + 1)^| S | = 2^| S |.

Answer 2

Ich argumentiere, dass dieses Problem einfach zu lösen ist, wenn man es richtig betrachtet. Sie kümmern sich nicht um die Reihenfolge der Elemente, nur ob sie in einer Untermenge von nicht erscheinen.

Zählen Sie, wie oft jedes Element in der Menge angezeigt wird. Wie viele Teilmengen gibt es für die eine Elementmenge {A}? Offensichtlich gibt es nur zwei Sätze. Nehmen wir nun an, wir haben ein anderes Element, B, hinzugefügt, das von A verschieden ist, um die Menge {A, B} zu bilden. Wir können die Liste aller Sätze sehr einfach bilden. Nehmen Sie alle Mengen, die wir gebildet haben, nur mit A, und fügen Sie null oder eine Kopie von B hinzu. Wir verdoppeln die Anzahl der Mengen. Natürlich können wir Induktion verwenden, um zu zeigen, dass für N verschiedene Elemente die Gesamtzahl der Mengen nur 2^N ist.

Angenommen, einige Elemente erscheinen mehrmals. Betrachten Sie die Menge mit drei Kopien von A. Also {A, A, A}. Wie viele Teilmengen können Sie bilden? Auch das ist einfach. Wir können 0, 1, 2 oder 3 Kopien von A haben, also ist die Gesamtzahl der Teilmengen 4, da die Reihenfolge keine Rolle spielt.

Im Allgemeinen, für N Kopien des Elements A, werden wir mit N + 1 möglichen Teilmengen enden. Erweitern Sie das nun, indem Sie eine Anzahl M von Kopien von B hinzufügen. Also haben wir N Kopien von A- und M-Kopien von B. Wie viele Gesamtuntermengen gibt es? Ja, das scheint auch klar zu sein. Zu jeder möglichen Untermenge mit nur A (es gab N + 1 von ihnen) können wir zwischen 0 und M Kopien von B hinzufügen.

Also die Gesamtzahl der Teilmengen, wenn wir N Kopien von A und M Kopien von B haben, ist einfach. Es muss (N + 1) * (M + 1) sein. Wir können wiederum ein induktives Argument verwenden, um zu zeigen, dass die Gesamtzahl der Teilmengen das Produkt solcher Ausdrücke ist. Zählen Sie einfach die Gesamtzahl der Replikate für jedes einzelne Element, addieren Sie 1 und nehmen Sie das Produkt.

Sehen Sie, was mit der Menge {A, B, B} passiert. Wir erhalten 2 * 3 = 6.

Für die Menge {A, A, B, B}, erhalten wir 3 * 3 = 9.