Entwickler-Ecke :: Thema anzeigen - random(); in mehreren Bereichen mit gleichmäßiger Verteilung

JungerIslaender - Do 09.05.13 23:48
Titel: random(); in mehreren Bereichen mit gleichmäßiger Verteilung

Ich Bräuchte eine random funktion die nicht eine Zufallszahl aus nur einem Bereich sondern aus mehreren Bereichen ermittelt und dabei stochastisch korrekt funktioniert.
Meine Erste Überlegung war also:

Pseudo

Quelltext

1:
2:
3:
4:
5:

temp = random ( 0, anzahl Bereiche);
case of temp
0 then random (0, 10)
1 then random (11, 200)
...

Dabei fiel mir auf, dass das ganze nur dann stochastisch korrekt ist, wenn Alle Bereiche gleich gr0ß sind. Also ein bisschen überlegt und dann kam mir diese Idee:

Pseudo

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

start[0] = 0;
start[1] = 11;

end[0] = 10;
end[1]= 200;

function (array of int, array of int):int

sum = 0;

if length(start) == length(end)

for i = 0 to length(start) do {
if (start[i] < end[i])
sum = sum + (end[i] - start[i])
dif[i] = (end[i] - start[i])
rand = random(0, sum)
}

dif[length(dif)+1] = sum;

for i = 0 to length(dif) do {
if (rand => summe(dif[i])) and (rand=< summe(dif[i+1]))
then result = start[i]+ (rand - summe(dif[i]))
}

Ganz siche bin ich mir nurnoch mit der letzten Zeile nicht. Und ja ich weiss der Code ist schrecklich, aber bevor ich das ganze in php schreibe erstmal der Algorhitmus. Vielleicht geht das ganze ja Schneller anders oder besser.

MFG JungerIslaender
P.S. Wo ist DER Mathematiker wenn man ihn braucht :P

IhopeonlyReader - Fr 10.05.13 19:42

Random( High(Bereich) - Low(Bereich +1) +Low(Bereich)

müsste doch theoretisch stochastisch korrekt sein oder?

Tut mir leid, in Delphi wird nur 1 Parameter erwartet.., es wird dann eine Zahl zwischen -1 und dem angebenen Parameter zurückgeliefert..
Beispiel:
Random(13); liefert eine der folgenden Zahlen 0,1,2,3,4,5,6,7,8,9,10,11,12
Wie das in PHP ist weiß ich nicht, aber vielleicht reicht die erste Zeile als Hilfe..

Beispiel: Dein Bereich: von 200 bis 500
Random( 500 - 200 +1) + 200
+1, da sonst die Zahl 500 nicht erreicht werden könnte

jaenicke - Fr 10.05.13 20:51

Wo soll denn gleichmäßig verteilt werden? So, dass jede Zahl die selbe Wahrscheinlichkeit hat, oder so, dass jeder Bereich die selbe Wahrscheinlichkeit hat?

JungerIslaender - So 12.05.13 13:54

Jede Zahl soll die selbe Wahrscheinlichkeit haben. Dabei sind die Bereiche allerdings unterschiedlich gross. Also sowas wie:
random(0 -100; 105 - 130; 300 - 305)

Und in meinem oberen Versuch hab ich folgendes versucht umzusetzten:

Ich übergebe an eine Funktion 2 Arrays: start und end. Diese beinhalten die Bereiche.
Dann summiere ich die Differenzen der Bereiche und habe so einen Pool aus der ich eine Zufallszahl ziehe. Diese wird dann nur noch zum Schluss wieder auf ihre Ursprungs Größe gebracht. Da haperts allerdings noch.

IhopeonlyReader - So 12.05.13 17:06

achso :D
dann mach das so
Bereich := random(1-3);
if Bereich=1 then zahl := random(0 - 100)
else if Bereich=2 then zahl := random(105-130)
else if Bereich=3 then zahl := random(300-305)

FinnO - So 12.05.13 17:24

IhopeonlyReader hat folgendes geschrieben :

Bereich := random(1-3);
if Bereich=1 then zahl := random(0 - 100)
else if Bereich=2 then zahl := random(105-130)
else if Bereich=3 then zahl := random(300-305)

Zahlen in Bereich 1:
p(1) = 1/3 * 1/100 = 0.333%

Zahlen in Bereich 2:
p(2) = 1/3 * 1/25 = 1.33%

Zahlen in Bereich 3:
p(3) = 1/3 * 1/5 = 6.67%

Wie du siehst: Nein.

Marc. - So 12.05.13 17:26

Das wäre aber nicht gleichverteilt. Warum?
Beispiel: A := {0}, B := {1,2}

P("0") = P(X=A) * P(Y=0) = 0.5 * 1 = 0.5
Aber:
P("1") = P("2") = ... = 0.5 * 0.5 = 0.25 != 0.5

Besser also: Eine u.U. langsame Methode:

Quelltext

1:
2:

while not inGültigenBereich(zufallsVariable) do
zufallsVariable = random(0, N)

Wobei N = Maximum{A,B}

jaenicke - So 12.05.13 18:40

Ich würde das ganze so machen:

test.php

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

<html>
<head>
</head>
<body>
<?php
function randomInArray($starts, $ends)
{ 
  $rangeSize = 0;
  $arraySize = count($starts);
  $rangeSizes = $starts;
  for ($i = 0; $i < $arraySize; $i++)
  {
    $rangeSizes[$i] = $ends[$i] - $starts[$i] + 1;
    $rangeSize += $rangeSizes[$i];
  }
  $randomResult = rand(1, $rangeSize);
  $i = 0;
  while (($randomResult > $rangeSizes[$i]) && ($i < $arraySize))
    $randomResult -= $rangeSizes[$i++];
  return $starts[$i] + $randomResult;
}

$testStarts = array(100, 2000, 30000, 400000, 5000000); 
$testEnds = array(199, 2099, 30999, 409999, 5000009);
for ($i = 1; $i <= 1000; $i++)
  echo randomInArray($testStarts, $testEnds).'<br>';
?>
</body>
</html>

Erst die Anzahl der Zahlen ermitteln und dann auf die Bereiche normieren.

JungerIslaender - Mo 13.05.13 00:09

jaenicke hat folgendes geschrieben :

[html="test.php"]
while (($randomResult > $rangeSizes[$i]) && ($i < $arraySize))
$randomResult -= $rangeSizes[$i++];
return $starts[$i] + $randomResult;

Bis auf diesen Teil mit meiner Idee ja identisch. Aber genau da hatte ich noch probleme, werde das ganze morgen Testen. Vielen Dank schonmal. Und schon in PHP :P

Marc. hat folgendes geschrieben :

Quelltext

1:
2:

while not inGültigenBereich(zufallsVariable) do
zufallsVariable = random(0, N)

Wobei N = Maximum{A,B}

Würde auch funktionieren, kann aber theoretisch unendlich lange laufzeit haben.

Marc. - Mo 13.05.13 08:29

JungerIslaender hat folgendes geschrieben :

Würde auch funktionieren, kann aber theoretisch unendlich lange laufzeit haben.

Da sollte eigentlich nicht "besser" stehen. :P

Noch eine Alternative wäre, aus dem einzelnen Arrays ein großes zu machen und daraus eine Zufallszahl zu ziehen.

Quelltext

1:
2:
3:
4:

A := {a,...b}  B := {c,...d}   a,b,c,d \in N
C := A U B
r := Random(#C)  #Mächtigkeit der Menge
Zufallszahl := C[r]

Ich muss los!

IhopeonlyReader - Mo 13.05.13 15:27

du kannst natürlich auch die GesamtRange ausrechnen, daraus random und dann wieder zerlegen..

Bsp. Bereich 1 : 100- 200
Bereich 2 : 300- 400
Bereich 3 : 500- 700
GesamtRange besteht dann immer aus (Ende - Anfang +1)

Quelltext

1:
2:
3:
4:
5:
6:

(B1 = Bereich 1; .A = Anfang; .E = Ende
GR := (B1.E - B1.A +1) + (B2.E - B2.A +1) + (B3.E - B3.A +1);
Ergebnis := Random(GR);
if Ergebnis<=(B1.E-B1.A) then Ergebnis := Ergebnis + B1.A
 else if Ergebnis<=((B2.E-B1.A)+(B1.E-B1.A+1)) then Ergebnis := Ergebnis + B2.A - (B1.E - B1.A +1);
  else Ergebnis := Ergebnis + B3.A - (B1.E - B1.A +1) - (B2.E - B2.A +1);

JungerIslaender - Do 16.05.13 21:21

Funktioniert wunderbar vielen Dank. Ich werd jetzt das ganze nochmal statistisch überprüfen und hoffe das es dann immer noch stimmt:P

Vielen Dank und MFG JungerIslaender

EDIT:

PHP-Quelltext

1:
2:
3:
4:
5:

       echo'<pre>';
       for ($i = 1; $i <= 1000000; $i++) {
        $stat[randomInArray($testStarts, $testEnds)]++;
        }
      print_r($stat);

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:

Array
(
    [424] => 7633
    [394] => 7608
    [284] => 7451
    [436] => 7578
    [607] => 7707
    [222] => 7490
    [261] => 7493
    [431] => 7695
    [393] => 7334
    [313] => 7646
    [283] => 7388
    [422] => 7582
    [342] => 7658
    [312] => 7552
    [532] => 7540
    [453] => 7579
    [626] => 7500
    [314] => 7381
    [121] => 7600
    [392] => 7567
    [316] => 7493
    [242] => 7531
    [493] => 7568
    [347] => 7542
    [432] => 7626
    [232] => 7500
    [456] => 7480
    [622] => 7427
    [527] => 7409
    [352] => 7529
    [395] => 7540
    [343] => 7482
    [512] => 7457
    [349] => 7591
    [213] => 7474
    [492] => 7566
    [131] => 7458
    [272] => 7510
    [434] => 7510
    [608] => 7597
    [433] => 7566
    [286] => 7502
    [623] => 7557
    [274] => 7381
    [231] => 7479
    [378] => 7523
    [443] => 7559
    [288] => 7349
    [353] => 7530
    [464] => 7412
    [277] => 7528
    [377] => 7593
    [375] => 7375
    [317] => 7499
    [332] => 7577
    [632] => 7675
    [346] => 7478
    [465] => 7565
    [462] => 7433
    [122] => 7538
    [348] => 7425
    [463] => 7610
    [624] => 7498
    [233] => 7489
    [606] => 7629
    [454] => 7532
    [333] => 7319
    [273] => 7482
    [411] => 7509
    [225] => 7533
    [457] => 7498
    [442] => 7568
    [276] => 7462
    [212] => 7659
    [345] => 7584
    [285] => 7454
    [282] => 7557
    [526] => 7489
    [287] => 7467
    [251] => 7524
    [603] => 7418
    [124] => 7622
    [271] => 7490
    [372] => 7406
    [211] => 7481
    [241] => 7365
    [494] => 7548
    [625] => 7645
    [521] => 7556
    [253] => 7572
    [262] => 7536
    [421] => 7610
    [351] => 7572
    [525] => 7618
    [224] => 7515
    [252] => 7500
    [373] => 7548
    [425] => 7397
    [444] => 7387
    [111] => 7524
    [354] => 7628
    [522] => 7530
    [341] => 7468
    [315] => 7503
    [423] => 7430
    [371] => 7598
    [391] => 7462
    [311] => 7525
    [223] => 7557
    [445] => 7504
    [331] => 7382
    [452] => 7580
    [458] => 7519
    [604] => 7655
    [435] => 7475
    [376] => 7555
    [528] => 7537
    [221] => 7573
    [495] => 7504
    [605] => 7431
    [263] => 7674
    [275] => 7455
    [412] => 7550
    [523] => 7470
    [344] => 7501
    [374] => 7336
    [243] => 7518
    [455] => 7463
    [289] => 7525
    [281] => 7634
    [524] => 7600
    [123] => 7457
    [234] => 7412
)

Das einzige was mich jetzt wundert ist, warum Print_r nicht nach Index sortiert... Aber egal, denn das sieht so ganz gut aus.

IhopeonlyReader - Do 16.05.13 21:32

Welche hast du denn jetzt verwendet?

P.s: es gibt auch ein danke Button

JungerIslaender - Do 16.05.13 21:48

PHP-Quelltext

1:
2:
3:

$testStarts = array(110, 120, 130, 210, 220, 230, 240, 250, 260, 270, 280, 310, 330, 340, 350, 370, 390, 410, 420, 430, 441, 451, 461, 491, 511, 520, 531, 602, 621, 631); 

$testEnds =   array(110, 123, 130, 212, 224, 233, 242, 252, 262, 276, 288, 316, 332, 348, 353, 377, 394, 411, 424, 435, 444, 457, 464, 494, 511, 527, 531, 607, 625, 631);

P.S. Apropos Danke Button. Wo zur Hölle ist der Eigentlich. Wunder mich schon die ganze Zeit wo der hin ist.

Narses - Do 16.05.13 22:12

Moin!

JungerIslaender hat folgendes geschrieben :

P.S. Apropos Danke Button. Wo zur Hölle ist der Eigentlich. Wunder mich schon die ganze Zeit wo der hin ist.

Dafür musst du in den Einstellungen Ajax aktivieren. :idea: ;)

cu
Narses