Hallo zusammen,
gegeben ist folgende Problemstellung:
1) Eine gegebene Zahl N soll in M Teile (m_1, ..., m_M) zerlegt werden,
so dass die Summe dieser Teile wieder N ergibt. Sowohl N und M sind
jeweils vorgegeben.
Für dieses Problem kursieren bereits einige Algorithmen im Internet (s.
https://stackoverflow.com/questions/1581394/split-value-in-24-randomly-sized-parts-using-c-sharp
oder
https://stackoverflow.com/questions/14583566/split-number-in-random-parts)
nun habe ich aber noch folgende weitere Anforderen an die M Teile:
2) jeder Teil darf minimal den Wert 0 annehmen
3) jeder Teil darf maximal einen jeweils für jeden Teil separat
definierten Wert annehmen (max_1, ..., max_M)
Selbstverständlich wird nun N so gewählt, dass diese Bedingungen auch
erfüllt werden können.
Folgende triviale Lösung kam mir zuerst in den Sinn:
Für jeden Teil m_i wird nacheinander eine zufällige Zahl gewählt, so
dass m_i <= max_i, N nicht überschritten wird und mit den restlichen
Teilen noch N erreicht werden kann.
Diesen Ansatz habe ich einmal beispielhaft in C++ implementiert:
Allerdings bin ich nun mit der Verteilung der Werte noch nicht ganz
zufrieden. Dieses müssen zwar nicht zwingend uniform verteilt sein,
jedoch wäre eine etwas gleichmäßigere Verteilung wünschenswert.
So konvergieren für die Eingabe mit {1.0, 1.0, 1.0, 1.0, 1.0, 1.0} für
die Maximalwerte und N = 5.0 die Werte bspw. gegen: {0.5, 0.75, 0.875,
0.9375, 0.96875}. Dies ergibt sich auch schon prinzipbedingt aus obigen
Ansatz. Notfalls könnte ich die M Teile bei jedem Aufruf zuerst zufällig
umsortieren. Vielleich hat allerdings jemanden noch einen besseren
Ansatz.
Vielen Dank schon einmal,
Mike
> 1) Eine gegebene Zahl N soll in M Teile (m_1, ..., m_M) zerlegt werden,> so dass die Summe dieser Teile wieder N ergibt. Sowohl N und M sind> jeweils vorgegeben.> 2) jeder Teil darf minimal den Wert 0 annehmen> 3) jeder Teil darf maximal einen jeweils für jeden Teil separat> definierten Wert annehmen (max_1, ..., max_M)
Überseh ich was? Die ersten Element werden jeweils auf max gesetzt, bis
N erreicht ist (das letzte davon evtl kleiner als max), die restlichen
auf 0.
Ich würde erst allgemein alle Lösungen berechnen um eine Zahl in N Teile
zu zerlegen und dann zufällig eine der Lösungen auswählen.
Das mathematische Problem kommt aus dem Bereich der Zahlkompositionen.
Einen einfachen Ansatz findest du hier:
http://www.aconnect.de/friends/editions/computer/combinatoricode_g.html
unter "2.2.3. k-Partitionen mit Berücksichtigung der Reihenfolge,
kolexikographisch geordnet".
Allerdings ohne Maximalwert und mit 1 beginnend. Habe den Algorithmus
selbst so wie du ihn möchtest darauf aufbauend auch gebraucht und ihn
letzlich in LabVIEW implementiert. C/C++ kann ich dir nicht anbieten.
asdfasd schrieb:> Überseh ich was?Mario M. schrieb:> Ja, das "zufällig" in der Überschrift. ;-)
Die Forderung ist, wie sich nach und nach herausstellt, noch schärfer:
die Zahlen sollen nicht nur zufällig, sondern auch statistisch
gleichverteilt sein. Natürlich ist das nur begrenzt sinnvoll, wenn man 8
in 4 Teile teilen will wird man keine Gleichverteilung hinkriegen.
Mike M. schrieb:> 3) jeder Teil darf maximal einen jeweils für jeden Teil separat> definierten Wert annehmen (max_1, ..., max_M)
Wozu lauter verschiedene Grenzen? Das macht eine Lösung in fast allen
denkbaren Fällen unmöglich. Man kann ja sagen, so darf man die Werte
halt nicht wählen, aber das ist ja kein anwendbarer Algorithmus.
Georg
warum nicht für jedes feld einen zufälligen wert zwischen 0 und dem
jeweiligen Maximum ermitteln?
Anschließend wird die Summe der Einzelteile auf die gesuchte Zielsumme
skaliert.
Soll die Lösung aus ganzen Zahlen bestehen wird in diesem Schritt
jeweils abgerundet und der Rest auf eine zufällige Zahl aufaddiert
(wobei natürlich das maximum beachtet wird)
Edit:
code: