Kombinatorik: Anzahl möglicher Partitionen mit Einschränkungen

cooky451

Also kann man weiter definieren:
Es gibt u Farben, u <= n.
Weiter hat ein Objekt eine Farbe u_1 bis u_j, j = u.

In Code ist also eine Funktion gesucht, die das kann:

bool permNext(std::vector<std::vector<Object>> &objects)
{
  // Object::color() gibt dann die Farbe zurück.
}

Soweit korrekt?

Die Sache mit den Objekten war nur eine Analogie.
Mir ist jetzt eine bessere Beschreibung eingefallen.

Gegeben ist eine Multimenge von natürlichen Zahlen. Dieselbe Zahl kann mehrfach vorkommen (darum Multimenge).

Nun soll die Multimenge partitioniert werden. Die Partitionen können beliebig klein oder groß sein. Es muss jedoch gelten: in keiner Partition darf dieselbe Zahl mehrfach enthalten sein.

Beispiel: Die Multimenge sei M = {1,2,3,3}.
Folgende sind alle gültigen Partitionen (Trennung durch | gekennzeichnet):
1 | 2 | 3 | 3
1 | 2,3 | 3
1,2 | 3 | 3
1,3 | 2 | 3
1,3 | 2,3
1,2,3 | 3

In diesem Fall sind es 6 Möglichkeiten. Die Partitionierung "1,2 | 3,3" wäre ungültig, weil dort die 3 mehrfach in derselben Partition vorkommt.

Ich bin nun auf der Suche nach der Funktion N(M), die die Anzahl der Möglichkeiten angibt, wie man eine solche Partitionierung der Multimenge M durchführen kann.

Wie am Beispiel gesehen, gilt z.B. N({1,2,3,3}) = 6.

Eine obere Grenze stellt auf jeden Fall die Bell-Zahl B_|M| dar. Wenn kein Element in der Multimenge mehrfach vorkommt, dann ist dies auch die korrekte Lösung.

Prof84

~~Da kommst Du ohne Constraint Processing wohl nicht aus.

Lies Dir mal das durch:
http://www.cs.sjsu.edu/~pearce/modules/patterns/events/ConstraintNetworks.htm
~~

Du meinst wohl Anzahl der Sätze von Partitionierungen
a) vollstandig
b) restoptimiert

Korrektur:
Die Lösung ist trivial für B. Die Anzahl der Partionen pro Satz wird bestimmt durch die Farbe mit am häufigsten vorkommt.

Ich glaube du hast mich falsch verstanden.

Ich suche die Anzahl gültiger Partitionierungen.
(gültig = es gibt keine Partition, in der dieselbe Zahl mehrfach vorkommt)

Ein Beispiel habe ich ja gegeben. Für {1,2,3,3} gibt es 6 gültige Partitionierungen.

Prof84

FreedomSoul schrieb:

Ich glaube du hast mich falsch verstanden.

Ich suche die Anzahl gültiger Partitionierungen.
(gültig = es gibt keine Partition, in der dieselbe Zahl mehrfach vorkommt)

Ein Beispiel habe ich ja gegeben. Für {1,2,3,3} gibt es 6 gültige Partitionierungen.

Und das verstehe ich eben unter Sätze der Partitionierungen.
Partitionionen hast Du zwischen 2-4.

Suchst Du jetzt eine mathematische oder numerische Lösung?

Ich suche eine Möglichkeit, wie ich die Anzahl der möglichen Partitionierungen finden kann, ohne alle explizit zu generieren und dabei zu zählen. Das kann ich schon, wird aber sehr schnell langsam, da die gesuchte Zahl sehr schnell mit der Anzahl (verschiedener) Elemente in der Menge wächst.

Ein paar Beispiele für Mengen ohne wiederholt auftretende Elemente:

N({1}) = 1
N({1,2}) = 2
N({1,2,3}) = 5
N({1,2,3,4}) = 15
N({1,2,3,4,5}) = 52
N({1,2,3,4,5,6}) = 203
N({1,2,3,4,5,6,7}) = 877
N({1,2,3,4,5,6,7,8}) = 4140
N({1,2,3,4,5,6,7,8,9}) = 21147
N({1,2,3,4,5,6,7,8,9,10}) = 115975
N({1,2,3,4,5,6,7,8,9,10,11}) = 678570

Wie schon gesagt, das sind die Bellschen Zahlen B_|M|.

Wenn ein Element mehrfach auftritt:

N({1,1}) = 1
N({1,1,2}) = 2
N({1,1,2,3}) = 6
N({1,1,2,3,4}) = 21
N({1,1,2,3,4,5}) = 83
N({1,1,2,3,4,5,6}) = 363

Ich habe mir schonmal die Differenzen zur ersten Reihe angeschaut und bin dann darauf gestoßen: http://oeis.org/A087648

Wieder die Bellschen Zahlen, aber drei Stück davon "irgendwie" zusammengerechnet. Ich war noch nicht in der Lage, das zu verallgemeinern, noch nicht einmal auf Fälle, wo genau ein Element dreifach auftritt ...

meinst du nicht A087649 ?

da die Rekursionsgleichung für die Bell numbers

B_k = sum_{i=0}^{k-1} \binom{k-1}{i}*B_i

heißt, ist das doch nicht kompliziert zu berechnen ?

Die Bellschen Zahlen zu berechnen ist natürlich nicht kompliziert.

Aber wie ich schon gesagt habe, ist die Bellsche Zahl nur dann die korrekte Antwort, wenn jedes Element nur einmal in der Menge auftaucht.

Ich suche aber eine Formel für beliebige Multimengen, wo jedes Element beliebig oft vorkommen kann, jedoch nicht mehrfach in einer Partition sein darf.

Hi,

Sozusagen ist eine ungültige Partition wieder eine multimenge während eine gültige "nur" eine Menge ist?

Dann suchst Du doch nur die Anzahl der untermultimengen die auch mengen sind?

temp schrieb:

Hi,

Sozusagen ist eine ungültige Partition wieder eine multimenge während eine gültige "nur" eine Menge ist?

Ja, richtig.

temp schrieb:

Dann suchst Du doch nur die Anzahl der untermultimengen die auch mengen sind?

Nein.
Nehmen wir nochmal das Beispiel M = {1,2,3,3}.
Es gibt 6 gültige Partitionierungen, aber

{}
{1}
{2}
{3}
{1,2}
{1,3}
{2,3}
{1,2,3}

8 Untermengen (oder 7, wenn man die leere Menge weglässt).

Prof84

Das Problem ist Du hast eine "genetische" Info die Du im Lösungsansatz berücksichtigen musst. Deshalb will ich doch wieder zurück zum Constraint Network. Das ist dann mathematisch kaum zu lösen, sondern Du brauchst eine numerische Lösung.

Ich buzz jetzt mal ein bisschen für Google aus Constraint Processing | ISBN: 1558608907:
Look-Ahead Algo
+ State Space Search
+ Backtracking
+ LAA for Value selection
+ LAA for Variable Order

Jetzt schauen wir mal was wir im Netz frei finden ...

Verdammt, das Farbproblem ist sogar beschrieben auf S.125 Abb 5.4. Mal schauen ob ich was zur Anzahl der Permutationen finde ... stand by. :xmas1:

Habe nichts gefunden was da weiterhelfen könnte, Nur Pseudo-Algos ... Sorry.