Archiv verlassen und diese Seite im Standarddesign anzeigen : Kombinatorikproblem
Hallo alle zusammen,
ich möchte wissen, wie viele Teilmengen mit einer gegebnenen Kardinalität ich von einer Multimenge bilden kann. Die Reihenfolge der Elemente ist egal. Z.B. sei die Multimenge {a,a,b,b,c,c,c} und ich möchte wissen wie viele Teilmengen mit drei Elementen es gibt. Von Hand gemacht: {a,a,b}, {a,a,c}, {a,b,b}, {a,b,c}, {a,c,c}, {b,b,c}, {b,c,c}, {c,c,c} = acht Teilmengen. Es gibt eine Formel für "Kombinationen mit Zurücklegen", (http://de.wikipedia.org/wiki/Kombinatorik#Kombination_mit_Zur.C3.BCcklegen_.28Repetition.29) die mir fast die richtige Antwort gibt: (3+3-1)!/(3!*(3-1)!) = zehn. Die beiden Kombinationen, die zuviel sind, sind: {a,a,a} und {b,b,b}. Von a und b sind nur jeweils zwei Elemente vorhanden, also können diese Teilmengen nicht gebildet werden. Gibt es für das Problem eine "einfache" Lösung?
bullshit
07.09.2005, 21:57
Hallo alle zusammen,
ich möchte wissen, wie viele Teilmengen mit einer gegebnenen Kardinalität ich von einer Multimenge bilden kann. Die Reihenfolge der Elemente ist egal. Z.B. sei die Multimenge {a,a,b,b,c,c,c} und ich möchte wissen wie viele Teilmengen mit drei Elementen es gibt. Von Hand gemacht: {a,a,b}, {a,a,c}, {a,b,b}, {a,b,c}, {a,c,c}, {b,b,c}, {b,c,c}, {c,c,c} = acht Teilmengen. Es gibt eine Formel für "Kombinationen mit Zurücklegen", (http://de.wikipedia.org/wiki/Kombinatorik#Kombination_mit_Zur.C3.BCcklegen_.28Repetition.29) die mir fast die richtige Antwort gibt: (3+3-1)!/(3!*(3-1)!) = zehn. Die beiden Kombinationen, die zuviel sind, sind: {a,a,a} und {b,b,b}. Von a und b sind nur jeweils zwei Elemente vorhanden, also können diese Teilmengen nicht gebildet werden. Gibt es für das Problem eine "einfache" Lösung?
bei einer kombination mit zurücklegen kann sehr wohl {a,a,a} vorkommen auch wenn es nur 2 a's gibt. du legst sie ja zurück und kannst sie nocheinmal ziehen und das natürlich auch 3 mal.
bei einer kombination mit zurücklegen kann sehr wohl {a,a,a} vorkommen auch wenn es nur 2 a's gibt. du legst sie ja zurück und kannst sie nocheinmal ziehen und das natürlich auch 3 mal.
Das meinte ich mit "fast die richtige Antwort" :)
bullshit
07.09.2005, 23:03
Das meinte ich mit "fast die richtige Antwort" :)
aber bei diesem beispiel ist meiner meinung eher das problem das es mehrere gruppen gibt (2 a's,2 b's,3 c's) ... ich werd mal überlegen wie das funktionieren soll bzw wie man das berechnet
aber bei diesem beispiel ist meiner meinung eher das problem das es mehrere gruppen gibt (2 a's,2 b's,3 c's) ... ich werd mal überlegen wie das funktionieren soll bzw wie man das berechnet
Ich wollte das Beispiel mit den "Kombinationen mit Zurücklegen" nur angeführen, weil es für den Fall, dass alle Elemente mindestens so häufig vorkommen, wie die Kardinalität der Teilmenge ist, das Ergebnis einfach (mit dieser Formel) berechnet werden kann. Ob ich zurücklege, oder ich habe mehr Elemente, als ich verbrauchen kann kommt auf's gleiche raus. Aber bei mir ist das die Ausnahme. Ich habe normalerweise mehr Platz in der Teilmenge, als die einzelnen Element vorkommen. D.h. es gibt "viele" Kombinationen die nicht möglich sind. Auch die Formel für "Kombinationen ohne Zurücklegen" (http://de.wikipedia.org/wiki/Kombinatorik#Kombination_ohne_Zur.C3.BCcklegen) hilft nicht, weil dort alle Elemente unterscheidbar sind. Ich habe selbst schon eine Routine, die die Zahl rekursiv berechnet, aber bei kombinatorischen Problemen werden die Anzahlen schnell groß... will sagen nicht mehr "einfach" berechenbar.
Ich hoffe ich habe das Problem jetzt besser dargestellt.
Eine auf dem "Ziehen-mit Zurücklegen" basierende Formel passt auf keinen Fall als Lösung. Höchstens als obere Schranke. Nach dem, and was ich mich aus der Vorlesung (die schon etwas her ist) erinnere ist das einzige, was mir sinnig erscheint, ist eine Anwendung des Inklusions-Exklusions-Prinzips. Das kommt in der Berechnung aber eher teurer als eine vernünftige rekursive Funktion. Darum will ich das gar nicht in der ganzen Kompliziertheit ausarbeiten.
Zeig also ruhig mal deine Funktion und wir schauen, ob es nicht vielleicht noch eine bessere gibt. :)
Eine auf dem "Ziehen-mit Zurücklegen" basierende Formel passt auf keinen Fall als Lösung. Höchstens als obere Schranke. Nach dem, and was ich mich aus der Vorlesung (die schon etwas her ist) erinnere ist das einzige, was mir sinnig erscheint, ist eine Anwendung des Inklusions-Exklusions-Prinzips. Das kommt in der Berechnung aber eher teurer als eine vernünftige rekursive Funktion. Darum will ich das gar nicht in der ganzen Kompliziertheit ausarbeiten.
eine Inklusion-Exklusion-Lösung hat den Vorteil, das nicht Einzelne Kombinationen gezählt werden, sondern die Werte, die addiert/subtrahiert werden mithilfe von Formeln berechnent werden. In meinem Code unten wird das Problem des einzel Zählens deutlich.
Zeig also ruhig mal deine Funktion und wir schauen, ob es nicht vielleicht noch eine bessere gibt.
Mein Ansatz ist in Java programmiert. Bitte nicht daran stören, dass ich im folgenden Text Klassen und Instanzen nicht jedesmal deutlich trenne. Ich glaube, dass man aus dem Zusammenhang leicht erkennen kann, was gemeint ist.
Ich habe eine Klasse Element, welche einen Wert hat, der das Symbol repräsentiert und eine Anzahl, die angibt, wie häufig dieses Symbol vorkommt. Zusätzlich hat ein Element noch eine Hilfsvariable summe.
Um eine Menge zu bilden, werden Element in einem java.util.Vector gespeichert. Bevor ich mit dem Vector die Zählfunktion aufrufe werden die Elemente im Vector aufsteigend nach deren Häufigkeit (Anzahl) sortiert und danach die Hilfsvariable summe in jedem Element gesetzt, so dass sie die Anzahl dieses und aller folgenden Elemente im Vector entspricht. Hier der Code:
1 public class Element {
2 int wert; // das Symbol, das diese Element repraesentiert
3 int anzahl; // wie haeufig kommt das Element vor
4 int summe; // Hilfvariable fuer Zaehlfunktion; hier steht die Summe aus diesem und allen im Vector folgenden Elementen
5 }
6
7 public static BigInteger zaehle(Vector elemente, int ab, int raum) {
8 BigInteger ergebnis;
9 if (ab >= elemente.size()) { // letztes Elemente ueberschritten
10 ergebnis = BigInteger.ZERO;
11 } else {
12 Element e = (Element) elemente.elementAt(ab);
13 if (raum > e.summe) { // nicht mehr genug Elemente vorhanden, um den Raum zu fuellen
14 ergebnis = BigInteger.ZERO;
15 } else if (raum == e.summe) { // Elemente reichen fuer genau eine Kombination
16 ergebnis = BigInteger.ONE;
17 } else if (raum <= e.anzahl) { // diese und alle folgenden Elemente sind so haeufig vorhanden, dass die Anzahl der Kombinationen mit einer kombinatorischen Formel berechnet werden kann
18 ergebnis = kombi(elemente.size() - ab, raum);
19 } else {
20 ergebnis = BigInteger.ZERO;
21 for (int i = raum; i >= raum - e.anzahl; i--) {
22 ergebnis = ergebnis.add(zaehle(elemente, ab + 1, i));
23 }
24 }
25 }
26 return ergebnis;
27 }
Im Aufruf wird ein Wert von 0 für ab gesetzt und raum entspricht der Kardinalität der "Zielmengen" (s. erstes Posting). Wenn ich mir die Funktion angucke, dann wird zweimal ZERO und einmal ONE direkt zurückgeliefert. Sonst ist entweder in Zeile 18 der Fall eingetreten, dass dieses Element (Element im Vector bei Position ab) mindestens so häufige vorkommt, wie es Platz in raum gibt. Da die Elemente im Vector aufsteigend sortiert sind, gilt das auch für alle folgenden. Hier kann die Formel für "Kombinationen mit Zurücklegen" kombi(.) genommen werden. Oder es wird ab Zeile 21 eine Summe gebildet aus der Anzahl der Kombinationen ohne dem aktuellen Element plus der Anzahl der Kombinationen mit einmal dem aktuellen Element plus ... plus der Anzahl der Kombinationen mit allen der aktuellen Elemente. Diese Anzahlen werden gebildet, indem ich die Funktion rekursiv aufrufe und dafür sorge, dass das aktuelle Element nicht berücksichtigt wird (ab + 1 im Aufruf Zeile 22) und der zur Verfügung stehende Raum soweit schrittweise verkleinert wird, wie es aktuelle Elemente gibt (durch die for-Schleife).
Also das was ich am Ende zurückbekomme ist eine Summe aus ZERO, ONE und kombi(.). Ich habe BigInteger gewählt, weil die Ergebnisse schnell Werte annehmen, die nicht mehr mir long zu fassen sind. Zahlen, die mit mehreren/vielen KiloBit gespeichert werden sind möglich. Da liegt mein Problem: nur die Aufrufe von kombi(.) bringen mich meinem gewünschtem Ergebnis "richtig" näher.
Wenn ich obige Funktion mit raum = 10000 und 100 verschiedenen Elementen im Vector aufrufe, wird mein Rechner zu meiner Lebzeit nicht mehr fertig. Und das liegt nicht daran, das mein Rechner so langsam ist oder ich so alt bin :).
Wenn wir natürlich über so große Zahlen reden. Da ist "groß" ja eigentlich noch stark untertrieben. Meine Inklusions-Exklusionsidee fußt aber letztlich auf den gleichen Mengen wie bei deiner Rekursion (die ich wohl ebenso angesetzt hätte). Ich wollte eigenlch auch schon aufgeben, da kam mir noch ein Gedanke, der mich dann letztlich die ganze Nacht hirnen liess.
Nebenbei bemerkt sind unveränderliche BigInteger zum Rechnen vielleicht nicht so die erste Wahl (performancemäßig). Schau doch mal, ob es da nicht was besseres gibt. Oder kopier dir den Quelltext von MutableBigInteger in eine eigene Klasse. (Findet sich nicht in der Doku, ist package-private).
Aber zurück zu meiner Idee. Sie ist imho besser als die Rekursion, aber wird immer noch elendlich lange dauern. Vielleicht bringt sie aber auch dich oder andere auf weitere Verbesserungsideen.
Ich habe mir überlegt, wie man die Anzahl der gesamt existierenden Teilmengen berechnen kann. Hierzu fange ich mit der leeren Menge an und füge nach und nach die Elemente hinzu. Gleiche Elemente werden direkt hintereinander eingefügt.
Zu Anfang habe ich die leere Menge, mit genau einer Teilmenge. Beim Einfügen eines Elements habe ich nun zwei Fälle.
1. Ich füge ein Element e hinzu, das noch nicht vorhanden ist.
Jetzt kann ich für jede bereits existierende Teilmenge eine weitere durch hinzufügen von e erzeugen, d.h. die Anzahl der Teilmengen verdoppelt sich.
2. Ich füge ein Element e hinzu, dass ich bereits im vorigen Schritten einfügte.
Wieder entstehen durch Hinzufügen von e potentiell für jede existierende Menge eine neue. Aber für alle Teilmengen, die bereits vor dem vorigen Schritt existierten, wurde bereits eine solche Menge erzeugt. Wirklich neue Teilmengen erhalte ich also nur aus den im letzten Schritt neu erzeugten Teilmengen.
Damit lässt sich nun die Gesamtzahl der Teilmengen berechnen. Mal am Beispiel {2a, 2b, 3c}:
01 - leere Menge
02 - verdoppeln für erstes a
03 - +1 für das weitere a
06 - verdoppeln für erstes b
09 - +3 für das weitere b
18 - verdoppeln für erstes c
36 - +2*9 für die beiden weiteren c
Wenn es jetzt eine Formel gäbe, um von der Gesamtzahl auf die Anzahl der k-elementigen Mengen zu kommen, wären wir aus dem Schneider. Ich habe da aber meine Zweifel.
Allerdings läßt sich der Algorithmus so verändern, dass er Mengen unterschiedlicher Kardinalität gesondert berechnet. Dadurch vergrößert sich aber der Aufwand in jedem Schritt um den Faktor k :(
Bei Bedarf erkläre ich das noch bzw mache ein erklärendes Beispiel. (Aber wirklich nur bei Bedarf.)
Die Antwort auf deine ursprüngliche Frage nach einer "einfachen" Lösung würde ich inzwischen mit Überzeugung verneinen. ;)
Meine Inklusions-Exklusionsidee fußt aber letztlich auf den gleichen Mengen wie bei deiner Rekursion (die ich wohl ebenso angesetzt hätte).
Meine Inklusions-Exklusions-Variante sollte ungefähr so ablaufen:
Meine Multimenge besteht aus n Gruppen gleicher Elemente. Die Kardinalität der Zielmenge nenne ich k.
1. (Inklusion) Berechne die Anzahl der Kombinationen mit der "Kombinationen mit Zurücklegen"-Formel (k+n-1)!/(k!*(n-1)!). Wie du richtig bemerktest, ist das als eine Obergrenze zu sehen, die nur dann als Ergebnis stimmt, wenn jedes Element mindestens so häufig vorkommt wie k.
2. (Exklusion) Für jedes Element bilde die Differenz d aus k und der Anzahl dieses Elementes.
2.1 Ist d>0 ziehe 1 vom Ergebnis ab (die Kombi., die aus k mal dem Elemente besteht) == (0+(n-1)-1)!/(0!*((n-1)-1)!)
2.2 Ist d>1 ziehe n-1 vom Ergebnis ab (die K., die aus k-1 mal dem Element und eines der n-1 anderen besteht) == (1+(n-1)-1)!/(1!*((n-1)-1)!)
2.3 Ist d>2 ziehe (2+(n-1)-1)!/(2!*((n-1)-1)!) vom Ergebnis ab (die K., die aus k-2 mal dem Element bestehen und einer K. aus zweien der n-1 anderen)
2.4 Ist d>3 ziehe (3+(n-1)-1)!/(3!*((n-1)-1)!) vom Ergebnis ab (die K., die aus k-3 mal dem Element bestehen und einer K. aus dreien der n-1 anderen)
....
2.1-2.x sind nicht exklusiv, also etwas in der Art if (d>1)...; if (d>2)...; und *nicht* if (d>1)...; ELSE if (d>2)...;
Als Code vielleicht so: for (summe = 0, i = d; i > 0; i--) { summe += (i+(n-2)!)/(i!*(n-2)!); } ergebnis -= summe; Diese Summe entspricht (d+n-1)!/(d!*(n-1)!). Also ist "einfach" berechenbar.
3. (Inklusion zum zweiten mal) Durch das Abziehen in 2. habe ich aber auch möglicherweise K. doppelt abgezogen, nämlich dann, wenn die Summe aus der Anzahl zweier Elemente plus eins kleiner als k ist. Es müssen also die K. wieder hinzugezählt werde, bei denen die Summe zweier Anzahlen von Elementen kleiner als k ist.
4. (Exklusion zum zweiten mal) Leider habe ich in 3. möglicherweise wie in 1. jetzt wieder zu viel K. hinzu gezählt, nämlich die, bei denen die Summe der Anzahlen dreier Elemente plus zwei kleiner als k ist...
......
Es ist abzusehen, wie das weiter geht. Inklusion und Exklusion wechseln sich ab und die Anzahl der Elemente, deren Anzahlen summiert werden, nimmt zu. Irgendwann ist da ein Ende gefunden, denn wenn es keine K. von x Elementen gibt, deren Anzahlen zusammen kleiner als k sind, dann gibt es auch keine K für x+1 Elementen. Ich gestehe, dass ich mich noch nicht "getraut" habe, das zu implementiern. Darum suche ich nach einer einfacheren Lösung.
Aber zurück zu meiner Idee. Sie ist imho besser als die Rekursion, aber wird immer noch elendlich lange dauern. Vielleicht bringt sie aber auch dich oder andere auf weitere Verbesserungsideen.
Ich habe mir überlegt, wie man die Anzahl der gesamt existierenden Teilmengen berechnen kann. Hierzu fange ich mit der leeren Menge an und füge nach und nach die Elemente hinzu. Gleiche Elemente werden direkt hintereinander eingefügt.
Zu Anfang habe ich die leere Menge, mit genau einer Teilmenge. Beim Einfügen eines Elements habe ich nun zwei Fälle.
1. Ich füge ein Element e hinzu, das noch nicht vorhanden ist.
Jetzt kann ich für jede bereits existierende Teilmenge eine weitere durch hinzufügen von e erzeugen, d.h. die Anzahl der Teilmengen verdoppelt sich.
2. Ich füge ein Element e hinzu, dass ich bereits im vorigen Schritten einfügte.
Wieder entstehen durch Hinzufügen von e potentiell für jede existierende Menge eine neue. Aber für alle Teilmengen, die bereits vor dem vorigen Schritt existierten, wurde bereits eine solche Menge erzeugt. Wirklich neue Teilmengen erhalte ich also nur aus den im letzten Schritt neu erzeugten Teilmengen.
Damit lässt sich nun die Gesamtzahl der Teilmengen berechnen. Mal am Beispiel {2a, 2b, 3c}:
01 - leere Menge
02 - verdoppeln für erstes a
03 - +1 für das weitere a
06 - verdoppeln für erstes b
09 - +3 für das weitere b
18 - verdoppeln für erstes c
36 - +2*9 für die beiden weiteren c
Wenn es jetzt eine Formel gäbe, um von der Gesamtzahl auf die Anzahl der k-elementigen Mengen zu kommen, wären wir aus dem Schneider. Ich habe da aber meine Zweifel.
Ich habe eine Zeit darüber gebrütet, aber ich sehe leider auch nicht, wie diese Zahl (die Anzahl der paarweise verschiedenen Teilmengen) zu der Anzahl der paarweise verschiedenen Teilmengen einer bestimmten Kardinalität führt. Es ist schon zum Mäusemelken, da hat man eine Formel für die Anzahl der Teilmengen ein gegebenen Kardinalität (binominal Koeffizient), aber dort sind die Mengen teilweise nicht unterscheidbar. So dicht dran, aber doch so weit entfernt.
Allerdings läßt sich der Algorithmus so verändern, dass er Mengen unterschiedlicher Kardinalität gesondert berechnet. Dadurch vergrößert sich aber der Aufwand in jedem Schritt um den Faktor k
Bei Bedarf erkläre ich das noch bzw mache ein erklärendes Beispiel. (Aber wirklich nur bei Bedarf.)
Ich habe an meiner rekursiven Funktion etwas "rumgespielt" und durch das cachen von Ergebnissen eine Geschwindigkeitssteigerung um den Faktor Tausend erreicht. Ob das jetzt ein konstanter Faktor ist muß siche erst noch zeigen. Wenn es der Fall ist, werde ich vielleicht das Inklusions-Exklusions-Verfahren ausprobieren. Wenn dass auch nicht in round-about linearer Zeit berechenbar ist, habe ich noch einen Plan B. Ich brauche die Anzahl aller Kombinationen um eine bestimmte Kombination zu benennen. Dazu müssen die Anzahlen viele male berechnet werden. Das heißt das Verfahren zum Berechenen sollte schon "ziemlich schnell" sein. Sonst werde ich die spezielle Teilmenge, die ich benennen möchte einfach durch eine Auflistung der Anzahl der einzelnen Elemente definieren. Dadurch verbrauche ich im Durchschnitt allerdings mehr Platz, als wenn ich eine Kombination durch eine Zahl definiere. Da das alles Teil eines Kompressionsprogrammes ist, ist das eine wichtige Eigenschaft. Andererseits kann man nicht hundert Jahre rechnen, um ein Bit "rauszuquetschen".
Die Antwort auf deine ursprüngliche Frage nach einer "einfachen" Lösung würde ich inzwischen mit Überzeugung verneinen.
Eine klare Antwort (auch wenn sie nein lautet) hilft mir mehr als viele ginge, könnte und vielleichts!
vBulletin® v3.8.6, Copyright ©2000-2012, Jelsoft Enterprises Ltd.