Verlosung

[puwu]

Ich habe zur Zeit folgende Tabelle:

id|username|lose
1|Hans|10
2|Franz|1
3|Manfred|100

Ich möchte eine Verlosung machen und der Gewinner soll zufällig (RAND()) ausgewählt werden. Nur mein Problem ist, wie kann mit SQL die Wertigkeit der Einträge bestimmen.

Ich meine, im o.g. Bespiel müßte id3 im Vorteil sein, weil er die meisten Lose gekauft hat.

Ich stehe leider irgendwie auf dem Schlauch. Könnte mir vielleicht jemand weiter helfen !?

SELECT FROM verlosung WHERE RAND() LIMIT 1 

Danke, schonmal im vorras

[ChrisB]

gewichteter zufall - Google Search

[mermshaus]

Ich habe mal versucht, in SQL was zu basteln:

<pre>
<?php

/*

--
-- Table structure for table `dw`
--

CREATE TABLE IF NOT EXISTS `dw` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `weight` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=5 ;

--
-- Dumping data for table `dw`
--

INSERT INTO `dw` (`id`, `name`, `weight`) VALUES
(1, 'marc', 2),
(2, 'stefan', 1),
(3, 'peter', 4),
(4, 'tim', 3);

*/

$q = "
SELECT
        derived.name
--
-- Ergebnismenge mit Spalte für kumulierte Gewichte bilden
-- (http://www.oracle.com/technology/oramag/code/tips2005/052305.html)
--
FROM
    (
        SELECT
                b.id,
                b.name,
                b.weight,
                SUM(a.weight) AS cum_weight
        FROM
                dw a,
                dw b
        WHERE
                a.id <= b.id
        GROUP BY
                b.id,
                b.weight
    ) AS derived
--
-- Dieselbe Zufallszahl r mit 0 <= r < SUM(weight) zu jeder Zeile hinzufügen
--
INNER JOIN              
    (
        SELECT
                FLOOR(RAND() *
                    (
                        SELECT
                                SUM(weight)
                        FROM
                                dw
                    )
                ) AS rand
    ) AS tmp
ON
        1
--
-- Diejenigen Zeilen auswählen, für die die Zufallszahl unter der bis dato
-- kumulierten Gewichtung liegt
--
WHERE
        tmp.rand < derived.cum_weight
--
-- Davon die Zeile mit dem kleinsten kumulierten Gewicht zurückgeben
--
ORDER BY
        derived.cum_weight ASC
LIMIT
        0,1";

mysql_connect('localhost', '', '');
mysql_select_db('test');

$results = array();

for ($i = 0; $i < 10000; $i++) {
    $res = mysql_query($q);

    $row = mysql_fetch_assoc($res);
    $results[$row['name']]++;
}

ksort($results);

print_r($results);

Beispielausgabe:

Array
(
    [marc] => 2005
    [peter] => 4105
    [stefan] => 996
    [tim] => 2894
)

Verbesserungen willkommen.

[Chriz]

SELECT * FROM verlosung ORDER BY RAND()*lose DESC LIMIT 1? Wer 100 Lose kauft hat nunmal auch 100x mehr Chancen auf den Gewinn als jemand mit einem.

[mermshaus]

@Chriz: Ich hätte ehrlichgesagt gedacht, das klappt, aber mein Test ging anders aus.

Zwei Teilnehmer:

Teilnehmer A: 2 Lose
Teilnehmer B: 1 Los

Erwartet: 66.6% zu 33.3%
Test: 75% zu 25%

Teilnehmer A gewinnt bei RAND() zwischen 0.5 und 1.0 automatisch, bei 0.0 bis 0.5 besteht zumindest noch eine 50%-ige Chance. (Der Faktor 2 macht daraus 0.0 bis 1.0, was genau das Werte-Intervall ist, das Teilnehmer B erreichen kann.)

[Chriz]

Ich bin mir nichtmal sicher ob der bei unter 0.5 wirklich bei 50% liegt. Bist du wirklich mit Testlaeufen zu den 75% / 25% gekommen?

[ChrisB]

Bist du wirklich mit Testlaeufen zu den 75% / 25% gekommen?

Das kannst du auch genauso gut mit einem PHP-Script nachvollziehen, dass für beide Teilnehmer jeweils eine Zufallszahl zwischen 0 und 1 auswürfelt, die des zweiten dann verdoppelt - und dann jeweils den mit dem höheren Wert gewinnen lässt.

$gewinn = array('t1' => 0, 't2' => 0);

for($i=0; $i<10000; ++$i) {
  $zufall1 = rand()/mt_getrandmax(); // normalisiert auf 0 bis 1
  $zufall2 = rand()/mt_getrandmax() * 2;
  if($zufall1 > $zufall2) { $gewinn['t1']++; }
  else { $gewinn['t2']++; } // den extrem seltenen Fall Gleichheit mal aussen vor
}

print_r($gewinn);
echo $gewinn['t1'] / $i .' : '. $gewinn['t2'] / $i; 

ergibt bspw.

Array
(
    [t1] => 2543
    [t2] => 7457
)
0.2543 : 0.7457

Das Problem ist, dass du hier nicht einen Zufallswert auswertest, sondern zwei voneiander unabhängige.
Wenn wir aber sagen, die Chancen sollen 1:2 verteilt sein, dann bezieht sich das auf einen Zufallswert.

[Chriz]

Scheint zu stimmen, welcher Algorithmus wäre dann korrekt?

[Flor1an]

Ja mathematisch ist es nicht das selbe. Wenns dich interessiert, die Technik nennt sich: Lotterie-Scheduling – Wikipedia
Da gibts auch nen PDF unten wo der Algorithmus erklärt wird.

[puwu]

@Chriz: Für meine Zwecke sollte das erstmal reichen, ich werde den Alogrytmus aber evt. noch verbessern.

Danke an alle die mit gewirkt haben!!