Wahrscheinlichkeiten bei N Würfen eines Würfels berechnen
Eine Übersetzung aus dem Englischen. Original von 
Rob van Wijk
Chen Shapira verwies mich auf ein SQL Rätsel von Iggy Fernandez. Laurent Schneider hat bereits eine beeindruckend einfache Lösung mittels hierarchischer Abfrage und der XMLQuery Funktion gezeigt. Ich verwendete die SQL Model Clause (natürlich) um dasselbe Ergebnis zu erzielen:
SQL> select * from die order by face_id
2 /
FACE_ID FACE_VALUE PROBABILITY
---------- ---------- -----------
1 1 ,25
2 3 ,25
3 4 ,25
4 5 ,083333333
5 6 ,083333333
6 8 ,083333333
6 Zeilen ausgewählt.
SQL> var N number
SQL> exec :N := 2
PL/SQL-Prozedur erfolgreich abgeschlossen.
SQL> with number_of_dies as (select count(*) cnt from die)
2 , all_probabilities as
3 ( select sum_value
4 , prob
5 , i
6 from (select level l from number_of_dies connect by level <= power(cnt,:N))
7 , number_of_dies
8 model
9 reference r on (select face_id, face_value, probability from die)
10 dimension by (face_id)
11 measures (face_value,probability)
12 main m
13 partition by (l rn, cnt)
14 dimension by (0 i)
15 measures (0 die_face_id, 0 sum_value, 1 prob, l remainder)
16 rules iterate (1000) until (iteration_number + 1 = :N)
17 ( die_face_id[0] = 1 + mod(remainder[0]-1,cv(cnt))
18 , remainder[0] = ceil((remainder[0] - die_face_id[0] + 1) / cv(cnt))
19 , sum_value[0] = sum_value[0] + face_value[die_face_id[0]]
20 , prob[0] = prob[0] * probability[die_face_id[0]]
21 )
22 )
23 select sum_value "Sum"
24 , sum(prob) "Probability"
25 from all_probabilities
26 group by rollup(sum_value)
27 order by sum_value
28 /
Sum Probability
---------- -----------
2 ,0625
4 ,125
5 ,125
6 ,104166667
7 ,166666667
8 ,104166667
9 ,125
10 ,048611111
11 ,055555556
12 ,048611111
13 ,013888889
14 ,013888889
16 ,006944444
1
14 Zeilen ausgewählt.
SQL> exec :N := 3
PL/SQL-Prozedur erfolgreich abgeschlossen.
SQL> with number_of_dies as (select count(*) cnt from die)
2 , all_probabilities as
3 ( select sum_value
4 , prob
5 , i
6 from (select level l from number_of_dies connect by level <= power(cnt,:N))
7 , number_of_dies
8 model
9 reference r on (select face_id, face_value, probability from die)
10 dimension by (face_id)
11 measures (face_value,probability)
12 main m
13 partition by (l rn, cnt)
14 dimension by (0 i)
15 measures (0 die_face_id, 0 sum_value, 1 prob, l remainder)
16 rules iterate (1000) until (iteration_number + 1 = :N)
17 ( die_face_id[0] = 1 + mod(remainder[0]-1,cv(cnt))
18 , remainder[0] = ceil((remainder[0] - die_face_id[0] + 1) / cv(cnt))
19 , sum_value[0] = sum_value[0] + face_value[die_face_id[0]]
20 , prob[0] = prob[0] * probability[die_face_id[0]]
21 )
22 )
23 select sum_value "Sum"
24 , sum(prob) "Probability"
25 from all_probabilities
26 group by rollup(sum_value)
27 order by sum_value
28 /
Sum Probability
---------- -----------
3 ,015625
5 ,046875
6 ,046875
7 ,0625
8 ,109375
9 ,09375
10 ,125
11 ,098958333
12 ,104166667
13 ,088541667
14 ,057291667
15 ,05787037
16 ,032986111
17 ,027777778
18 ,012731481
19 ,008680556
20 ,006944444
21 ,001736111
22 ,001736111
24 ,000578704
1
21 Zeilen ausgewählt.
Und mit einem traditionellen Würfel:
SQL> update die
2 set face_value = face_id
3 , probability = 1/6
4 /
6 Zeilen wurden aktualisiert.
SQL> select * from die order by face_id
2 /
FACE_ID FACE_VALUE PROBABILITY
---------- ---------- -----------
1 1 ,166666667
2 2 ,166666667
3 3 ,166666667
4 4 ,166666667
5 5 ,166666667
6 6 ,166666667
6 Zeilen ausgewählt.
SQL> with number_of_dies as (select count(*) cnt from die)
2 , all_probabilities as
3 ( select sum_value
4 , prob
5 , i
6 from (select level l from number_of_dies connect by level <= power(cnt,:N))
7 , number_of_dies
8 model
9 reference r on (select face_id, face_value, probability from die)
10 dimension by (face_id)
11 measures (face_value,probability)
12 main m
13 partition by (l rn, cnt)
14 dimension by (0 i)
15 measures (0 die_face_id, 0 sum_value, 1 prob, l remainder)
16 rules iterate (1000) until (iteration_number + 1 = :N)
17 ( die_face_id[0] = 1 + mod(remainder[0]-1,cv(cnt))
18 , remainder[0] = ceil((remainder[0] - die_face_id[0] + 1) / cv(cnt))
19 , sum_value[0] = sum_value[0] + face_value[die_face_id[0]]
20 , prob[0] = prob[0] * probability[die_face_id[0]]
21 )
22 )
23 select sum_value "Sum"
24 , sum(prob) "Probability"
25 from all_probabilities
26 group by rollup(sum_value)
27 order by sum_value
28 /
Sum Probability
---------- -----------
3 ,00462963
4 ,013888889
5 ,027777778
6 ,046296296
7 ,069444444
8 ,097222222
9 ,115740741
10 ,125
11 ,125
12 ,115740741
13 ,097222222
14 ,069444444
15 ,046296296
16 ,027777778
17 ,013888889
18 ,00462963
1
17 Zeilen ausgewählt.
SQL> exec :N := 4
PL/SQL-Prozedur erfolgreich abgeschlossen.
SQL> with number_of_dies as (select count(*) cnt from die)
2 , all_probabilities as
3 ( select sum_value
4 , prob
5 , i
6 from (select level l from number_of_dies connect by level <= power(cnt,:N))
7 , number_of_dies
8 model
9 reference r on (select face_id, face_value, probability from die)
10 dimension by (face_id)
11 measures (face_value,probability)
12 main m
13 partition by (l rn, cnt)
14 dimension by (0 i)
15 measures (0 die_face_id, 0 sum_value, 1 prob, l remainder)
16 rules iterate (1000) until (iteration_number + 1 = :N)
17 ( die_face_id[0] = 1 + mod(remainder[0]-1,cv(cnt))
18 , remainder[0] = ceil((remainder[0] - die_face_id[0] + 1) / cv(cnt))
19 , sum_value[0] = sum_value[0] + face_value[die_face_id[0]]
20 , prob[0] = prob[0] * probability[die_face_id[0]]
21 )
22 )
23 select sum_value "Sum"
24 , sum(prob) "Probability"
25 from all_probabilities
26 group by rollup(sum_value)
27 order by sum_value
28 /
Sum Probability
---------- -----------
4 ,000771605
5 ,00308642
6 ,007716049
7 ,015432099
8 ,027006173
9 ,043209877
10 ,061728395
11 ,080246914
12 ,096450617
13 ,108024691
14 ,112654321
15 ,108024691
16 ,096450617
17 ,080246914
18 ,061728395
19 ,043209877
20 ,027006173
21 ,015432099
22 ,007716049
23 ,00308642
24 ,000771605
1
22 Zeilen ausgewählt.
Über die Lösung: sie generiert so viele Zeilen wie es Kombinationen gibt (power(cnt,:N)). Mit der die_face_id und den verbleibenden Größenwerten (measures), wird jede generierte Zeile in N face_id's mit N Wiederholungen umgewandelt. Der face_value und die Wahrscheinlichkeiten werden über ein Referenz Modell geholt. Zuletzt summiert nur noch die äußere Abfrage alle Wahrscheinlichkeiten.
Die SQL Sprache ist nicht "komplett", aber seit Version 10 wundere ich mich ernsthaft ob es Probleme gibt, die nicht mit SQL gelöst werden können. Auch wenn es für manche wie eine Breze (die pretzel, die von Steven Feuerstein erwähnt wurde) wirkt bin ich sicher, dass es mit einigen Kommentaren gar nicht so schwer wartbar ist.
oracle@matzberger.de Für Kontakte aller Art, auch Fehlermeldungen zum Tutorial
Impressum