Zufall mit mehreren Variablen, aber gleichem Gesamtwert

Xaby · Beitrag von **Xaby** » 22.10.2008 15:43

Folgendes.

Sagen wir, wir haben 2 Zahlen.

Jede darf einen Wert zwischen 0 und 100 einnehmen.

Aber der Gesamtbetrag aus der Summe der beiden, soll gleich bleiben.

Also: A = 34 und B = 70
A+B = 104
Summe aus A+B ist "S"

A wird Random(100) und B=S-A

Damit erhält man zwei zufällige Zahlen, aber der Gesamtbetrag bleibt gleich.

Wie gestaltet man das aber nun mit drei oder mehreren Zahlen?

3 Werte?

Z=A+B+C

A=45
B=30
C=80

S=155

A ist wieder zufällig

Angenommen A wird 99

Aber wie groß sind B und C?

dann bleiben für C+B noch 56 übrig

B wird also eine Zahl zwischen 0 und 56

C ist dann die Differenz.

---------------------------------

Was aber, wenn nun A=0 ist

Dann bleiben für B+C die gesamten 155 übrig

Und man kann jetzt nicht mehr sagen, dass B einfach eine Zahl zwischen
0 und 155 ist, da B ja nur zwischen 55 und 100 sein darf.

Hier geht es auch noch. B ist einfach eine zufällig Zahl und C ist die Differenz zu 155.

----------------------------

Aber nun machen wir ein WorstCaseSenario

A=95
B=85
C=70

In der ersten Runde wird A zufällig 30

Die Differenz zwischen 250 und 30 beträgt nur 220

Selbst wenn B und C je hundert wären, würde das nicht mehr ausreichen.

Also müsste man schon hier A auf 50 in der untersten Möglichkeit eingrenzen.

Jemand eine Ahnung, wie man einen eleganten Allgorithmus findet, der diese Überprüfungen mit einer beliebigen Anzahl an Variablen (Array oder Liste) machen kann.

Vorgaben der Prozedur bräuchten nur die einzelnen Limits sein und die Gesamtsumme

Also Mache(Limit, Summe)

Und die Prozedur teilt die Summe entsprechend zufällig auf alle in der Liste oder dem Array befindlichen Variablen auf, mit der Berücksichtigung, dass das Limit nicht überschritten wird.

Das Limit könnte sein: 100, 255 (bei Farbwerten), oder jede andere Zahl.

STARGÅTE · Beitrag von **STARGÅTE** » 22.10.2008 15:51

irgendwie verstehe ich deine ganzen Regeln nicht ...

Wieso müssen die einzelnen Zahlen auch in einem Bereich liegen ?

Und man kann jetzt nicht mehr sagen, dass B einfach eine Zahl zwischen
0 und 155 ist, da B ja nur zwischen 55 und 100 sein darf.

nur damit die Erste Zahl nicht = Summe wäre und dann alle anderen 0 sein müssten ?

also willst du das bei 10 Zahlen und der Summe 1000 alle zahlen um die 100 liegen ja ?

ZeHa · Beitrag von **ZeHa** » 22.10.2008 16:05

Kannst Du den ungefähren Einsatzzweck beschreiben? Vielleicht führt uns das schneller zu einer Lösung...

STARGÅTE · Beitrag von **STARGÅTE** » 22.10.2008 16:08

hier mal meine Version:

Sie beachtet dabei das alle Zufallszahlen "frei" ermittelt werden und am ende dann nur noch etwas erhöht oder vertieft werden um auf die SUMME zu kommen.
Denn eine nacheinander erzeugung führt vermutlich dazu das am ende immer sehr kleine zahlen kommen oder nicht "freie"

Code: Alles auswählen

Procedure Mache(Anzahl, Summe)
 Durchschnitt = Summe/Anzahl
 Dim Array(Anzahl)
 For n = 1 To Anzahl
  Array(n) = Random(Durchschnitt)+Durchschnitt/2
  Pos + Array(n)
 Next
 Faktor.f = Summe/Pos
 Pos = 0
 For n = 1 To Anzahl
  Array(n) = Int(Array(n)*Faktor)
  Pos + Array(n)
 Next 
 While Pos < Summe 
  z = Random(Anzahl-1)+1
  If Array(z) < Summe
   Array(z) + 1 : Pos + 1
  EndIf
 Wend
 While Pos > Summe 
  z = Random(Anzahl-1)+1
  If Array(z) > 0
   Array(z) - 1 : Pos - 1
  EndIf
 Wend
 For n = 1 To Anzahl
  Debug Array(n)
 Next 
EndProcedure

Mache(3, 100)
Debug "---"
Mache(10, 1000)

sibru · Beitrag von **sibru** » 22.10.2008 16:33

was hälste hiervon:

Code: Alles auswählen

Procedure Mache(Anzahl, Summe)
  Dim Array(Anzahl)
  While Anzahl ;von unten nach oben (spart ´ne LaufVariable...)
    If Anzahl>1 ;nicht letztes Element:
      Array(Anzahl) = Random(Summe/Anzahl) ;Random aus aktuellem Durchschnitt
    Else : Array(Anzahl)=Summe ;letztes Element kriegt den Summen-Rest
    EndIf
    Summe-Array(Anzahl) ;Summen-Rest pflegen
    Debug Array(Anzahl)   
    Anzahl-1 ;...und auf zur Nächsten
  Wend
EndProcedure

Mache(3, 100)
Debug "---"
Mache(10, 1000)

Ist zwar keine 100%ige NormalVerteilung, kommt aber schon nah´ ´dran...

Gruss Siggi...

Froggerprogger · Beitrag von **Froggerprogger** » 22.10.2008 16:47

Das Problem (das auch schon angesprochen wurde) ist folgendes:
Du musst die gewünschte Zufallsverteilung bestimmen, z.B.:
1. Sollen die verfügbaren Einheiten etwa gleichmäßig (uniform) auf alle verteilt werden?
Bsp: Verteile auf 10 Elemente, Limit 100, Summe 10 liefert z.B.(0,1,1,2,0,2,1,1,1,1)
2. Oder sollen wie in Deinem Verfahren beschrieben die ersten Variablen bevorzugt werden, in dem Sinne, dass ihnen stets bis max. das volle Limit zur Verfügung steht?
Bsp: Verteile auf 10 Elemente, Limit 100, Summe 10 liefert z.B.(8,1,0,1,0,0,0,0,0,0)
3. Oder...(viele andere Verteilungen denkbar)?

Hier ein Beispiel für die exakt uniforme (gleichmäßige Verteilung) mit lahmer Laufzeit O(sum) und eines für eine annähernd uniforme Verteilung mit Laufzeit O(sum/limit), die aber doch tendenziell weiter gestreut ist, also im obigen Beispiel wird sowas wahrscheinlicher wie (0,0,3,1,0,1,4,0,0,1)

Code: Alles auswählen

CompilerIf #PB_Compiler_Version <= 420 ; Definiere ArraySize()-Hack für PB <= 4.20
  Procedure.l ArraySize(*A.l)
    ProcedureReturn PeekL(*A-8)
  EndProcedure
CompilerEndIf

Procedure.l Min(a.l, b.l)
  If a > b
    ProcedureReturn b
  Else
    ProcedureReturn a
  EndIf
EndProcedure

Procedure.l Max(a.l, b.l)
  If a > b
    ProcedureReturn a
  Else
    ProcedureReturn b
  EndIf
EndProcedure

Procedure.l FillRandom(A.l(1), limit.l, sum.l, uniform.l)
 
  If ArraySize(A()) * limit < sum
    ProcedureReturn #False
  EndIf

  remainSum.l = sum
  n.l = ArraySize(A())
  While remainSum > 0
    curIndex.l = Random(n-1)
   
    If uniform
      curVal.l = 1 ; use only portion of 1 => uniform distribution
    Else
      curVal.l = Max(1, Random(Min(limit, remainSum/n))) ; use bigger portions => no longer uniform
    EndIf
   
    If A(curIndex) +curVal < limit
      A(curIndex)+curVal
      remainSum-curVal
    EndIf
  Wend

  ProcedureReturn #True
EndProcedure

;- example
sizeA.l = 10
Dim A.l(sizeA)

FillRandom(A(), 200, 1000, #True)

Debug "uniform"
For i=0 To ArraySize(A())-1
  Debug A(i)
Next

Dim A.l(sizeA)

FillRandom(A(), 200, 1000, #False)

Debug "near uniform"
For i=0 To ArraySize(A())-1
  Debug A(i)
Next

'Idee' ganz Banane: Verteile jeden Summenpunkt einzeln auf ein zufällig ausgewähltes Element, solange bei diesem limit noch nicht erreicht wurde. => schön uniform
Ansonsten verteile nicht einzeln, sondern zufällige Pakete bis maximal Größe limit oder restSumme/AnzahlElemente (je nachdem, was kleiner ist). => annähernd uniform

Kaeru Gaman · Beitrag von **Kaeru Gaman** » 22.10.2008 18:01

ZeHa hat geschrieben:Kannst Du den ungefähren Einsatzzweck beschreiben? Vielleicht führt uns das schneller zu einer Lösung...

+1

kswb73 · Beitrag von **kswb73** » 22.10.2008 18:31

Ich hab mal STARGÅTEs, sibrus und Froggerprogger Codes geprüft. Zusätzlich noch einen Testcode(siehe unten). Die Tests sind mit dem von Xaby angegebenen Beispiel durchgeführt. Bei anderen Bedingungen schneiden sie anders ab. (Bsp: STARGÅTEs Code wird bei großen Zahlen und Froggerproggers Code bei vielen Zahlen langsamer)

Verteilung der Werte
Hier der Testcode und Froggerproggers Code (nicht uniform) am besten ab. Die einzelnen Ergebnisse konnten tatsächlich zwischen 0 und 100 liegen.
Bei STARGÅTEs Code lagen die Ergebnisse mittig zwischen 0 und 100. Man hatte nach nur selten kleine oder große Ergebnisse.
Dannach folge Froggerproggers Code (uniform). Hier lagen die Ergebnisse sogar noch enger beieinander als bei STARGÅTEs Code. Hier ist so gut wie unmöglich 0 oder 100 zu erreichen.
An letzter Stelle steht sibrus Code. Ein Ergebniss lag immer unter 50, die Anderen beiden immer über 50. Sie waren recht gleimäßig.

Geschwindigkeit
Hier schnitt sibrus Code am besten ab.
Froggerproggers
STARGÅTEs und Froggerproggerss (nicht uniform) Codes waren etwa 40% langsamer.
Froggerproggerss Code (uniform) war etwa 35% langsamer.
Der Testcode war etwa 9 mal langsamer als STARGÅTEs Code.

Testcode
Der Sinn des Testcodes war es zu testen ob es Sinnvoller ist immer ein Punkt von einer Zufällig ausgewählten Zahl abzuzieh/hinzuzufügen.

Code: Alles auswählen

Anzahl=3
Global Dim Array(Anzahl)

Procedure Mache(Anzahl, Summe)
 Durchschnitt = Summe/Anzahl
 For n = 1 To Anzahl
  Array(n) = Random(Durchschnitt)+Durchschnitt/2
  Pos + Array(n)
 Next
 Faktor.f = Summe/Pos
 Pos = 0
 For n = 1 To Anzahl
  Array(n) = Int(Array(n)*Faktor)
  Pos + Array(n)
 Next
 While Pos < Summe
  z = Random(Anzahl-1)+1
  If Array(z) < Summe
   Array(z) + 1 : Pos + 1
  EndIf
 Wend
 While Pos > Summe
  z = Random(Anzahl-1)+1
  If Array(z) > 0
   Array(z) - 1 : Pos - 1
  EndIf
 Wend
EndProcedure 

#MaxZ=100

InitSprite()
InitKeyboard()

Dim Test(3,1024)

For n=1 To 1024
mache(3,150)
gZ1=Array(1)
gZ2=Array(2)
gZ3=Array(3)

test(1,n)=gZ1;/n
test(2,n)=gZ2;/n
test(3,n)=gZ3;/n
Next n

OpenScreen(1024,768,32,"Test")
Repeat
ClearScreen(0)
ExamineKeyboard()
  If KeyboardPushed(#PB_Key_Escape)
  End
  EndIf
  
  If KeyboardPushed(#PB_Key_LeftShift)
  speed=20
  Else
  speed=5
  EndIf
  
  If KeyboardPushed(#PB_Key_Left)
  viewX-speed
  EndIf
  
  If KeyboardPushed(#PB_Key_Right)
  viewX+speed
  EndIf

StartDrawing(ScreenOutput())
  For N=1 To 3
  L=Test(n,1)
    For a=2 To 1024
      Select n
        Case 1
        color=$FF0000
        Case 2
        color=$00FF00
        Case 3
        Color=$0000FF
      EndSelect
    LineXY((a-1)*5-viewX,L*768/#MaxZ,a*5-viewX,test(n,a)*768/#MaxZ,Color)
    L=test(n,a)
    ;Debug L
    Next a
  Line(0,768/2,1024,0,$FFFFFF)
  Next n
StopDrawing()

FlipBuffers()
ForEver

Xaby · Beitrag von **Xaby** » 22.10.2008 18:46

Den Einsatz-Zweck habe ich mit Absicht nicht angegeben, weil die Sache dann zu sehr in eine Richtung gelaufen wäre und die Diskussionen über Alternativen den Threat unnötig belastet hätten.

Sinn und Zweck der Sache ist, dass eine Gesamtmenge zufällig verteilt wird.

Angenommen, wir haben 5 Körbe mit Äpfeln.

In jeden Korb passen maximal 10 Äpfel.

Wir kippen alle Körbe auf einen Haufen und zählen diese Äpfel.
Dann bekommen wir heraus, dass wir 32 Äpfel haben.

Nun möchte ich diese 32 Äpfel wieder auf die 5 Körbe verteilen.
Aber zufällig.

Eine Möglichkeit wäre ja auch, die 5 Körbe zu nehmen und einfach den Inhalt zu tauschen. Das reicht aber noch nicht aus, um zufällig genug zu sein.

Wenn man nur 3 Körbe hat, wo je 5 Äpfel drin sind, würde ein Tauschen keinen Sinn ergeben.

Die Frage nach dem Sinn, die könnte man sich sicherlich stellen, aber darum geht es doch bei der Informatik. Ein Problem zu lösen, ohne den Sinn dahinter kennen zu müssen.

Froggerprogger · Beitrag von **Froggerprogger** » 22.10.2008 19:10

Froggerproggers Code konnt ich leider nicht testen, da er bei mir nicht lieft (hab 4.2).

Hab hier 4.3 Beta 3. Woran liegt das denn, vielleicht an ArraySize? Habe mal obigen Code geändert, so dass bei Version <= 4.20 auch ArraySize funktionieren sollte. Ansonsten: Arrays als Parameter gibt es schon bei 4.20? Schau mal einfach, ob es nun klappt.