Diese Seite verwendet Cookies, um die Navigation auf unserer Website zu verbessern. Durch Weiternutzung unserer Seite stimmst du der Verwendung von Cookies zu. Weitere Details dazu und Einstellungsmöglichkeiten findest du in unseren Cookie-Richtlinien und unserer Datenschutzerklärung.Schließen

Menge der Lösungen bestimmen - Kombinatorik

    • str1fenhoernchen
      str1fenhoernchen
      Bronze
      Dabei seit: 23.10.2010 Beiträge: 142
      Hallo zusammen,

      ich habe folgendes Problem, das mir recht einfach scheint, ich jedoch nicht auf die Lösung komme.

      Ich habe n Währungen und ein Cent-Inkrement von x. Gesucht ist die Funktion f(n,x)=1, die alle möglichen Lösungen ermittelt, die in Summe 1 Geldeinheit (GE) ergeben.

      Ein Beispiel:
      3 Währungen und das Inkrement ist 50 Cent, also f(3,50)=6. Die Lösungen sind 3x je 1GE einer Währung und 50Cent Währung 1/2, 50Cent Währung 1/3, 50Cent Währung 2/3.

      Mit dem Binomialkoeefizienten und bloßem drauf schauen bin ich hier leider nicht weiter gekommen. Welche anderen Lösungsansätze könnte ich mir anschauen? Mir einem Excel-Tool ausrechnen wäre natürlich kein Problem. Für mich ist allerdings der analytische Weg interessant.

      Ich freue mich falls jmd. eine Idee hat.
      Grüße,
      Str1fenhörnchen
  • 10 Antworten
    • Rho0
      Rho0
      Bronze
      Dabei seit: 20.10.2008 Beiträge: 727
      das problem ist ein cousin des knapsack problems. ich kann mir gut vorstellen, dass es hierfür keine generelle formel geben kann.
    • str1fenhoernchen
      str1fenhoernchen
      Bronze
      Dabei seit: 23.10.2010 Beiträge: 142
      Danke für die Anregung. Bin ich aus dem Stand nicht drauf gekommen.
    • Metter3330
      Metter3330
      Bronze
      Dabei seit: 12.03.2007 Beiträge: 5.605
      Ich glaube man muss nur richtig zählen. Ich würde mir das etwa so vorstellen:
      w_1,w_1,w_1, w_2, w_3,w_3,.....,w_n,w_n,w_n
      Gemeint ist hier 3 Einheiten der Größe x von Währung 1, dann eine Einheit der Größe x von Währung 2 usw.
      Insgesamt hast du praktisch M=1/x "Slots" auf die du die Währungen verteilen musst (ich denke man sollte annehmen, dass 1/x eine natürliche Zahl ist). Und damit du nichts doppelt zählst, soll das ganze so sein, dass du einfach nur sagen musst, bis zu welchem Slot du mit w_1 auffüllst, dann bis wohin mit w_2 usw.
      In Kombinatorik schreibt man solche Sachen häufig um in einer Art, die sich "bars and stars" nennt. Hier kannst du das oben im Prinzip auch so schreiben:
      ***|*|**|....|**
      D.h. letztlich geht es darum zu sagen wo die Striche | sein sollen. D.h. du musst n-1 Striche verteilen auf M+1 Positionen (links vom ersten Stern und rechts vom letzten können auch Striche stehen). Im Sinne vom Urnenmodell heißt das im Prinzip, dass wir M+1 verschiedene Kugeln haben und n-1 mal ziehen mit zurücklegen und ohne Beachtung der Reihenfolge (d.h. (1,2,4) = (2,1,4) etc.). Dafür gibt es n-1+M+1 -1 über n-1 Möglichkeiten. D.h. mit M=1/x:
      f(n,x) = n-1 + 1/x über n-1
      Ich hoffe das ist halbwegs verständlich...
    • Rho0
      Rho0
      Bronze
      Dabei seit: 20.10.2008 Beiträge: 727
      dein ansatz funktioniert - wenn überhaupt - nur bei fällen, die eine lösung zulassen. nimm eine währung mit einer 33 cent-münze. hier gibt es keine lösung.
      dein ansatz scheitert daran, dass du bei deiner kombination nicht überprüfst, ob die summe 1 erreicht wird. deshalb sehe ich auch die verwandtschaft zum knapsack problem, denn die summe 1 - eigenschaft ist im prinzip sowas wie die rucksack - voll - eigenschaft.
    • Metter3330
      Metter3330
      Bronze
      Dabei seit: 12.03.2007 Beiträge: 5.605
      Ok, dann haben wir vermutlich die Frage unterschiedlich interpretiert. Also du gehst davon aus, dass jede Währung eine unterschiedliche Grundeinheit x hat? Ja, dann wird man sicher keine einfache Formel finden können. Das sehe ich auch so.

      Ich dachte wir haben n Währungen und jeweils die gleiche Grundeinheit x wie im Beispiel. Wenn 1/x dann keine natürliche Zahl ist, gibt es natürlich keine Lösung. Das meinte ich damit, dass man 1/x € IN annehmen sollte. Unter diesen Voraussetzungen braucht man dann praktisch genau 1/x Cent Stücke um auf eine Geldeinheit zu kommen. Und dann muss man nur noch schauen von welcher Währung man wieviele nimmt.
    • str1fenhoernchen
      str1fenhoernchen
      Bronze
      Dabei seit: 23.10.2010 Beiträge: 142
      x, also cents sind nicht weiter teilbar und daher natürliche Zahlen. Es ist schon so, dass eine unterschiedliche Anzahl cents je Währung zulässig ist. Also 34+16+50=100.

      Die Gesamtmenge der Lösungen des Rucksackproblems wird mit 2^n angegeben, wobei n für die "möglichen Rucksackobjekte" steht. Die Angabe von x als Inkrement scheint daher nicht zielführend zu sein um zur Anzahl der möglichen Objekte zu kommen.

      Ein Ansatz der leider nicht funktioniert aber vlt hilft:
      Ein Inkrement von 50 führt zu 3 Möglichkeiten je Währung (0,50,100). Die Menge aller Objekte ist bei 3 Währungen dann 9. 2^9 ist allerdings nicht richtig, da nicht alle 9 miteinander kombinierbar sind. Sondern immer ein Tripel mit einem Wert je Währung gebildet werden muss.
    • Metter3330
      Metter3330
      Bronze
      Dabei seit: 12.03.2007 Beiträge: 5.605
      Das ist ja genau das was ich gemacht habe.

      Also hier in deinem Beispiel: Du schreibst jetzt Inkrement 50. Das entspricht x = 0.5 in Bezug auf die Grundeinheit. Sonst kann sich ja nicht alles zu 1 aufsummieren. D.h. bei diesem Inkrement und 3 Währungen ergibt meine Formel
      3 - 1 + 1/0.5 über 3 - 1 = 4 über 2 = 6
      mögliche Kombinationen. Und die sind gegeben durch (jeweils Anteil erste bis dritte Währung)
      (1, 0, 0)
      (0.5, 0.5, 0)
      (0.5, 0, 0.5)
      (0, 1, 0)
      (0, 0.5, 0.5)
      (0, 0, 1)
    • str1fenhoernchen
      str1fenhoernchen
      Bronze
      Dabei seit: 23.10.2010 Beiträge: 142
      Ich glaube wir haben da das selbe Verständnis.

      Ich habe mich nochmal an den Ansätzen der Kombinbatorik versucht. Der Lösungsansatz "Ziehen mit zurücklegen ohne Reihenfolge" gibt die richtige Anzahl an Lösungen aus. So richtig erklären warum kann ich mir jedoch nicht.
      Hier gibt's nen Onlinerechner: http://www.ingo-bartling.de/mathe/klasse12/html/stochastik/kombinatorik.html

      Beispielhafte Lösungen:
      n=Anzahl Währungen
      k=100/Cent-Inkrement

      n k Lösungen
      1 1 1
      1 2 1
      1 10 1
      1 100 1
      2 1 2
      2 2 3
      2 10 11
      2 100 101
      3 1 3
      3 2 6
    • Metter3330
      Metter3330
      Bronze
      Dabei seit: 12.03.2007 Beiträge: 5.605
      Ok, ich versuche nochmal zu erklären was ich oben meinte. Hab mal ein paar ganz billige Sachen mit Paint gemalt ;)
      Also stell dir vor du hast ein Inkrement von 20 Cent (bzw. 0,2). Dann brauchst du praktisch immer 5 20 Cent Münzen, um auf eine Geldeinheit zu kommen.
      Das meinte ich oben mit "Slots":

      Du musst praktisch jedes x durch eine 20 Cent Münze ersetzen, dann hast du insgesamt eine Geldeinheit. Nimm mal an es gibt 3 Währungen (rot, grün und blau).
      Dann sieht das etwa so aus:

      D.h. hier sind es 2 mal 20 Cent aus Währung "rot" und "grün" und 1 mal 20 Cent aus Währung "blau".

      Hier jetzt 4 mal grün, 1 mal blau.

      Zuletzt noch nur grün und ich habe mal unten drunter die Balken nummeriert (jetzt kommt das was ich oben "stars and bars" genannt habe).

      Zu obigen Zeichnungen ist es praktisch äquivalent, dass du einfach die Stellen sagst, bis wohin die Farben rot und grün gehen. D.h. im ersten Fall rot bis Balken 3 und grün bis Balken 5. Blau ergibt sich dann ja automatisch. Wir haben also ein Tupel (3, 5).
      In der zweiten Grafik entsprechend (1, 5) (rot geht bis Balken 1, kommt also nicht vor).
      In der dritten Grafik hast du (1, 6).

      Und so wird jeder solcher Verteilung auf die Slots genau ein solches Paar von Zahlen zugeordnet (wobei wir immer annehmen, dass wir zuerst mit rot auffüllen, dann mit grün und zuletzt mit blau). Umgekehrt: Wenn du irgendein paar von Zahlen vorlegst, dann kannst du wieder eine Grafik wie oben daraus "rekonstruieren". Z.B. (4,5) ergibt

      Oder (4,1) liefert

      Die Zahlen können auch gleich sein, denn z.B. (3,3) ergibt

      D.h. unser Problem hat sich massiv vereinfacht. Wir müssen nur noch zählen wieviele Paare (m,n) von Zahlen es gibt, wobei m,n jeweils Zahlen aus {1,2,3,4,5,6} sind. Und dabei unterscheiden wir nicht zwischen z.B. (3,4) und (4,3), weil die kleinste der Zahlen immer angeben soll bis wohin rot aufgefüllt wird. Und das ist eben genau Ziehen mit Zurücklegen ohne Reihenfolge.

      Wenn du jetzt mehr Farben bzw. Währungen hast, dann hast du statt paaren von Zahlen entsprechend längere Tupel. Z.B. bei 10 Währungen bekommst du 9-Tupel usw.
      Und das Inkrement legt fest wieviele Balken du hast. Wenn 5 mal das Inkrement eine Geldeinheit ergibt, dann hast du 6 Balken. Ergibt 100 mal das Inkrement eine Geldeinheit, dann bekommst du 101 Balken.
    • str1fenhoernchen
      str1fenhoernchen
      Bronze
      Dabei seit: 23.10.2010 Beiträge: 142
      Wow, vielen Dank für die ausführliche Erklärung! Ich weiß die Mühe (und die Paint Skillz) sehr zu schätzen :f_love:

      Auch allen anderen vielen Dank für die Unterstützung!