[PHP] Random item met kanspercentage

[Verwijderd]

Ik zit met een probleemvraagje.

Ik wil een x aantal items hebben die random uitgekozen worden.
Maar dan wil ik niet zoiets als :

PHP:

$wil = rand(1, 4);

switch($wil){
      case 1: $bla = "item1";
      break;
      case 2: $bla = "item2";
      break;
      case 3: $bla = "item3";
      break;
      case 4: $bla = "item4";
      break;
}

Maar dan met een bepaald kanspercentage. Dus dat bijv zoiets als :

20% item 1
10% item 2
30% item 3
40% item 4

Ik heb er al veel over nagedacht. Misschien dat er wel een bepaalde functie is waarmee ik dit kan maar dat weet ik niet. Geen idee waarnaar ik moet zoeken n.l..

Ik zat al te denken if( $var >= 30 AND $var < 45 ){ bla.
Maar dat lijkt me een hele omslachtige methode voor iets wat simpeler moet kunnen.

Ik hoop dat iemand al eens met dit bijltje gehakt heeft en een leuke suggestie heeft.

Bij voorbaat dank.

P.S. nogmaals ik heb al gegoogled, maar kwam nergens op uit omdat ik simpelweg niet weet waarnaar ik moet zoeken.

[ Voor 1% gewijzigd door André op 09-08-2006 14:25 ]

[André]

Volgens mij is de methode die je aangeeft perfect.

Verder verplaats ik dit topic naar Programming

[DataGhost]

PHP:

<?php 
$wil = rand(1, 10); 

switch($wil){ 
      case 1: 
      case 2: 
            $bla = "item1"; 
            break; 
      case 3: 
            $bla = "item2"; 
            break; 
      case 4: 
      case 5: 
      case 6: 
            $bla = "item3"; 
            break; 
      case 7: 
      case 8: 
      case 9: 
      case 10: 
            $bla = "item4"; 
            break; 
} 
?>

zo?

[remcotolsma]

Een switch-case constructie is misschien niet heel handig. Je zou het ook met een array kunnen oplossen:

PHP:

$item1 = 'Item 1';
$item2 = 'Item 2';
$item3 = 'Item 3';

$items = array();
// $item1 2x keer toevoegen
$items[] = $item1;
$items[] = $item1;
// $item2 3x keer toevoegen
$items[] = $item2;
$items[] = $item2;
$items[] = $item2;
// $item3 5x keer toevoegen
$items[] = $item3;
$items[] = $item3;
$items[] = $item3;
$items[] = $item3;
$items[] = $item3;

$random = rand(0, count($items));
echo $items[$random];

Het mag wel duidelijk zijn dat hoe vaker een item in de array staat hoe groter de kans is dat deze er uit gekozen wordt.

Eventueel zou je een functie kunnen maken die een item net zo vaak toevoegd aan de $items array totdat de kanspercentage voor dat item bijvoorbeeld 40% is.

[The - DDD]

Is inderdaad ook wat ik meestal doe wanneer er een kans van toepassing is.

In Java maak ik dan in ieder geval een List/array aan waar alle items in verhouding in zitten.

In jouw specifieke geval is een array met met 2 + 1 + 3 + 4 = 10 voldoende. Vervolgens een ramdom waarde bepalen tussen 0(incl.) en 10 (excl.). Voordeel is dat het redelijk generiek is. Je pakt een random onder de lengte van je List/array de exacte vulling maakt voor je "prijsschieter" niet echt uit dat is aan de aanroepende kant van belang.

Je overhead is met deze oplossing volgens mij ook redelijk klein. Enkel een referentie naar de betreffende waarde is voldoende, ook bij complexe typen. Ik denk ook niet dat er manieren zijn die sneller, zuiniger of beter werken.

[ Voor 18% gewijzigd door The - DDD op 09-08-2006 15:05 ]

[NMe]

OMG @ remcotolsma (en in mindere mate @ DataGhost). Ik heb nog nooit zo'n omslachtige methode gezien om een kans te berekenen.

PHP:

$wil = rand(1, 100);

if ($wil < 20) {
      $bla = "item1";
} else if ($wil < 30) {
      $bla = "item2";
} else if ($wil < 60) {
      $bla = "item3";
} else {
      $bla = "item4";
}

Lijkt me net even iets handiger dan een array gaan vullen met loze waarden.

[Tofu]

Ik gebruik dezelfde manier als -NMe-, alleen dat mijn waarden dan in een database staan, maar dat doert er niet veel toe. Alleen als je het doet zoals -NMe- dan moet je wel <= ipv < gebruiken of rand(0, 99); (denk ik)?

[NMe]

tofu schreef op woensdag 09 augustus 2006 @ 15:25:
Ik gebruik dezelfde manier als -NMe-, alleen dat mijn waarden dan in een database staan, maar dat doert er niet veel toe. Alleen als je het doet zoals -NMe- dan moet je wel <= ipv < gebruiken of rand(0, 99); (denk ik)?

Klopt, foutje van mijn kant.

[Verwijderd]

Voordeel van de methode die The -DDD gebruikt ten opzichte van die -NMe- gebruikt is wel dat de eerste generieker is en het aantal verschillende opties met de bijbehorende percentages er niet hardcoded in staan

[crisp]

best of both worlds:

PHP:

$items = array(
    'item1' => 20,
    'item2' => 10,
    'item3' => 30,
    'item4' => 40
);

$rand = rand(1, 100);
$totalchance = 0;
reset($items);
foreach ($items as $item => $chance)
{
    $totalchance += $chance;
    if ($rand <= $totalchance) break;
}

echo $item;

[Voutloos]

Een magisch getal door een variabele vervangen (of 1 nieuwe variabele met een cumulatieve waarde) lijkt me het probleem niet, T162.

edit:
En Crisp heeft inmiddels al een cumulatieve var erin gewerkt.

[ Voor 22% gewijzigd door Voutloos op 09-08-2006 15:34 ]

[Verwijderd]

Voutloos schreef op woensdag 09 augustus 2006 @ 15:34:
Een magisch getal door een variabele vervangen (of 1 nieuwe variabele met een cumulatieve waarde) lijkt me het probleem niet, T162.

Buiten het magic number verhaal heb je een er hard coded een aantal if statements in staan wat ook niet echt flexibel is. Maar zoals je al opmerkte heeft Crisp een mooie oplossing neergezet.

[.oisyn]

crisp schreef op woensdag 09 augustus 2006 @ 15:32:
best of both worlds:

Nou alleen nog even die rand(1,100) vervangen door code die het totaal berekent van je array en dat als maximum van de rand neemt

[NMe]

.oisyn schreef op woensdag 09 augustus 2006 @ 15:55:
[...]

Nou alleen nog even die rand(1,100) vervangen door code die het totaal berekent van je array en dat als maximum van de rand neemt

Hoeft ook niet als je maar zorgt dat die som altijd netjes op 100% uitkomt.

[.oisyn]

Dat suckt. Wat als je nou een trekking wilt simuleren uit een vaas met 10 rode en 25 witte balletjes. Grote jongen als jij dat met exact dezelfde verhouding op 100 uit kan krijgen . Bovendien is het niet erg werkbaar, je moet elke keer met de hand die verhoudingen aan gaan passen.

[ Voor 21% gewijzigd door .oisyn op 09-08-2006 16:15 ]

[Verwijderd]

crisp schreef op woensdag 09 augustus 2006 @ 15:32:
best of both worlds:

PHP:

$items = array(
    'item1' => 20,
    'item2' => 10,
    'item3' => 30,
    'item4' => 40
);

$rand = rand(1, 100);
$totalchance = 0;
reset($items);
foreach ($items as $item => $chance)
{
    $totalchance += $chance;
    if ($rand <= $totalchance) break;
}

echo $item;

Thnx!!, lijkt me een uistekende oplossing.

Nu nog ervoor zorgen dat wanneer de items in de array worden gezet dat je bijvoorbeeld lukraak procenten kunt geven en dat een scriptje ze opteld kijkt hoeveel percentage het afwijkt van 100 en dan met dat percentage terugbrengen naar waarden die samen 100 vormen. :-)

Ga als ik thuiskom vanaaf gelijk ff proberen.

(Het is voor en missie generator btw.)

[.oisyn]

Lees .oisyn in "[PHP] Random item met kanspercentage" nog 'ns, het hoeven natuurlijk geen percentages te zijn

[Voutloos]

Precies.

Verwijderd schreef op woensdag 09 augustus 2006 @ 16:49:
Nu nog ervoor zorgen dat wanneer de items in de array worden gezet dat je bijvoorbeeld lukraak procenten kunt geven en dat een scriptje ze optelt ...

...en dat je dat dan gewoon direct als max gebruikt voor rand().

[MBV]

crisp schreef op woensdag 09 augustus 2006 @ 15:32:
best of both worlds:

PHP:

$items = array(
    'item1' => 20,
    'item2' => 10,
    'item3' => 30,
    'item4' => 40
);

$rand = rand(1, array_sum($items));
$totalchance = 0;
reset($items);
foreach ($items as $item => $chance)
{
    $totalchance += $chance;
    if ($rand <= $totalchance) break;
}

echo $item;

is dit niet iets? PHP heeft al zoveel functies, geweldige taal

[.oisyn]

Heeft het geen lower_bound achtig iets? Niet dat dat efficienter is aangezien het hash maps zijn dus het blijft O(n), maar in C++ zou je zoiets doen:

C++:

struct item_t
{
    const char * name;
    int amount;
};

// de data
item_t items[] =
{
    "item1", 20,
    "item2", 10,
    "item3", 30,
    "item4", 40
};

// de map vullen
std::map<int, const char *> chancemap;
int total = 0;
for (int i = 0; i < sizeof(items)/sizeof(items[0]); i++)
{
    chancemap[total] = items[i].name;
    total += items[i].amount;
}

// een willekeurig item trekken
const char * item = chancemap.lower_bound(rand() % total);

Een lower_bound is gewoon een search op element <= key, maar omdat een map een binaire boom is kan dat dus in O(log N)

[MBV]

ik denk dat je aardig wat items moet hebben voor je die performancewinst eruit haalt Zoieso ga je het er niet uit halen, aangezien je eerst je map moet vullen waarbij je door je hele array heen loopt. Dat doe crisp beter: gemiddeld (beetje afhankelijk van de kansen ) zal die van crisp maar door de helft heen lopen.
Daarnaast gaat het vullen van je map fout omdat na 'item1' de waarde '20' komt, en jij maar 1 ophoogt. En rand() moet je volgens mij vermenigvuldigen met total, niet modulus
Als ik niet heel erg slaperig ben, ben ik beter van je gewend

[Soultaker]

Jeuj, off-topic:

.oisyn schreef op woensdag 09 augustus 2006 @ 21:48:
Heeft het geen lower_bound achtig iets? Niet dat dat efficienter is aangezien het hash maps zijn dus het blijft O(n), maar in C++ zou je zoiets doen:

C++:

// --------- 8< --------------
std::map<int, const char *> chancemap;
// ..
const char * item = chancemap.lower_bound(rand() % total);

Nog efficiënter: dezelfde data in een gesorteerde vector en dan met std::lower_bound een binary search doen. (Kan zelfs in PHP!)

MBV schreef op woensdag 09 augustus 2006 @ 23:02:
ik denk dat je aardig wat items moet hebben voor je die performancewinst eruit haalt Zoieso ga je het er niet uit halen, aangezien je eerst je map moet vullen waarbij je door je hele array heen loopt. Dat doe crisp beter: gemiddeld (beetje afhankelijk van de kansen ) zal die van crisp maar door de helft heen lopen.

Het idee is natuurlijk dat je de map één kaar maakt en dan heel vaak hergebruikt, maar als je 'm maar één keer per request nodig hebt werkt dat niet in PHP.

Daarnaast gaat het vullen van je map fout omdat na 'item1' de waarde '20' komt, en jij maar 1 ophoogt.

Elk element in de array is één item (met zowel een name als een amount). In de array initializer hoef je geneste arrays niet met braces te omringen, al is dat soms wel duidelijker. .oisyn's code is equivalent aan:

C++:

item_t items[] = 
{ 
    { "item1", 20 }, // items[0]
    { "item2", 10 }, // items[1]
    { "item3", 30 }, // items[2]
    { "item4", 40 }  // items[3]
};

Het vullen van de map gaat dus prima.

En rand() moet je volgens mij vermenigvuldigen met total, niet modulus

In C/C++ retourneert rand() een integer tussen 0 en RAND_MAX; om dat te makkelijk te mappen naar een bereik van 0 tot total kun je de modulus operator gebruiken. Vermenigvuldiging zou correct zijn als rand() een reëel getal tussen 0 en 1 zou retourneren. Wél kun je eventueel klagen over het feit dat de distributie van getallen van .oisyn's code niet uniform is en dat 'ie helemaal slecht werkt als total > RAND_MAX.

Als ik niet heel erg slaperig ben, ben ik beter van je gewend

Ik hoop op dat je deze reply na een goede nachtrust leest.

[ Voor 61% gewijzigd door Soultaker op 10-08-2006 06:44 ]

[.oisyn]

Soultaker schreef op donderdag 10 augustus 2006 @ 06:21:
Nog efficiënter: dezelfde data in een gesorteerde vector en dan met std::lower_bound een binary search doen. (Kan zelfs in PHP!)

Nóg efficienter: de data gesorteerd als binary heap, zodat je geen random access hebt in je array wat voor de eerste paar niveaus diep wat cache vriendelijker is (heeft geen nut in PHP)

Ik vraag me trouwens hoe het zit met de distributie van php's rand. Zal me niets verbazen als die gewoon op C's rand() bouwt (aangezien ze ook gewoon die RAND_MAX aanhouden)
.edit: yup, uit de source van php 5.1.4 (ext/standard/php_rand.h,rand.c)

C++:

#define RAND_RANGE(__n, __min, __max, __tmax) \
    (__n) = (__min) + (long) ((double) ( (double) (__max) - (__min) + 1.0) * ((__n) / ((__tmax) + 1.0)))

PHPAPI long php_rand(TSRMLS_D)
{
    long ret;

    if (!BG(rand_is_seeded)) {
        php_srand(GENERATE_SEED() TSRMLS_CC);
    }

#ifdef ZTS
    ret = php_rand_r(&BG(rand_seed));
#else
# if defined(HAVE_RANDOM)
    ret = random();
# elif defined(HAVE_LRAND48)
    ret = lrand48();
# else
    ret = rand();
# endif
#endif

    return ret;
}

PHP_FUNCTION(rand)
{
    long min;
    long max;
    long number;
    int  argc = ZEND_NUM_ARGS();

    if (argc != 0 && zend_parse_parameters(argc TSRMLS_CC, "ll", &min, &max) == FAILURE)
        return;

    number = php_rand(TSRMLS_C);
    if (argc == 2) {
        RAND_RANGE(number, min, max, PHP_RAND_MAX);
    }

    RETURN_LONG(number);
}

Dus niet per se C's rand, maar wel altijd PHP_RAND_MAX verschillende random waarden mappen op (max-min+1) mogelijke uitkomsten. Dezelfde fout dus.

[ Voor 64% gewijzigd door .oisyn op 10-08-2006 12:05 ]

[Soultaker]

.oisyn schreef op donderdag 10 augustus 2006 @ 11:44:
Nóg efficienter: de data gesorteerd als binary heap, zodat je geen random access hebt in je array wat voor de eerste paar niveaus diep wat cache vriendelijker is

Leg eens uit? In een heap zoals ik die ken, kun je niet zoeken.

Ik vraag me trouwens hoe het zit met de distributie van php's rand. Zal me niets verbazen als die gewoon op C's rand() bouwt (aangezien ze ook gewoon die RAND_MAX aanhouden)
..
Dus niet per se C's rand, maar wel altijd PHP_RAND_MAX verschillende random waarden mappen op (max-min+1) mogelijke uitkomsten. Dezelfde fout dus.

Lamers.

[.oisyn]

Soultaker schreef op donderdag 10 augustus 2006 @ 13:22:
[...]

Leg eens uit? In een heap zoals ik die ken, kun je niet zoeken.

Misschien de verkeerde term, met heaps haal ik die dingen om een of andere reden altijd door elkaar. Ik bedoel gewoon een binaire boom gemapped op een array. Als een node op positie x staat in de array, dan staat z'n parent op positie (x-1)/2 en z'n twee kinderen op de posities 2x+1 en 2x+2

[Soultaker]

Ah, een gebalanceerde binaire zoekboom in een array; wordt inderdaad ook voor implementatie van heaps gebruikt.

Dat lijkt heel erg op een gesorteerde lijst, ook qua zoekalgoritme; het enige verschil is dat je de elementen in pre-order (eerst node zelf, dan zijn kinderen) noteert, terwijl een gesorteerde lijst overeenkomt met in-order notatie (eerst de kleinere subtree, dan de node zelf, dan de grotere subtree). Dat geld alleen voor een gebalanceerde zoekboom trouwens, maar een niet-gebalanceerde zoekboom kun je ook niet handig in een array stoppen.

Ik kan me eigenlijk niet voorstellen dat dat qua performance veel verschilt van binair zoeken in een gesorteerde lijst, wat in feite ook overeenkomt met het zoeken in een gebalanceerde binaire boom. Het enige verschil is dat de elementen die je bekijkt op iets andere plekken staan, maar bij beide methoden halveer je elke iteratie het relevante deel van de lijst, en de grootte van de stappen die je neemt zijn ook hetzelfde, alleen ga je met de pre-order notatie van kleine naar grote stappen en met de binary search precies andersom. Is er een reden om aan te nemen dat dat efficiënter is?

[ Voor 34% gewijzigd door Soultaker op 10-08-2006 16:26 ]

[.oisyn]

Let wel, ik zei het met een knipoog, ik denk dat het in de praktijk maar weinig uitmaakt

Maar theoretisch heb je met een pre-order boom minder cachemisses omdat de kleine stappen tijdens het begin van het zoeken plaats vinden zodat je er altijd voordeel van hebt. Bij een in-order boom hoeft dat niet omdat je een element al kunt vinden voordat je aan een dergelijke kleine stapgrootte bent toegekomen.
Anderzijds kun je met een pre-order boom garanderen dat een kleine stap nooit een cache-boundary zal overschrijden als je 'm goed aligned, met een in-order boom kun je dat niet zeggen omdat de kleine stappen overal in de array plaats kunnen vinden.

Dus als je elk element in de boom een keer zoekt (en je invalidate je cache na elke search), heb je met een pre-order boom in totaal minder cache-misses dan met in-order boom. Maar zoals gezegd, het verschil is peanuts.

[Verwijderd]

Ik kom er niet uit..

Ik heb dit.

PHP:

<?PHP

$explode = explode("|","16|19|10|11|34|"); // waarde ids
array_pop($explode);

$explode2 = explode("|","65|64|60|45|5|"); // waarde percentages
array_pop($explode2);

$items = array_combine($explode, $explode2);

$rand = rand(1, 100);
$totalchance = 0;
reset($items);
foreach ($items as $item => $chance)
{
    $totalchance += $chance;
    if ($rand <= $totalchance) break;
}

echo $items; // krijg je de waarde ids te zien maar ik heb het ff over de percentages

?>

Nu is het probleem, ik krijg steeds die percentage 65 te zien of 64. Nooit die 60, terwijl de kans niet eens zo veel hoger is.. En die 45 heb ik nooit meer gezien.

Hoe kan ik dit eerlijk verdelen? Want ik wil dat ze ze allemaal laten zien, en die 5% is gewoon een zeldzaam kansje als je die krijgt.

Als ik 70% doe ipv 65 dan zie ik die 64 dus straks ook nooit meer..

Terwijl hier het wel gewoon werkt.

PHP:

<?php
$items = array(
    '30% kans' => 30,
    '1% kans' => 1,
    '10% kans' => 10,
    '80% kans' => 80
);

$rand = rand(1, 100);
$totalchance = 0;
reset($items);
foreach ($items as $item => $chance)
{
    $totalchance += $chance;
    if ($rand <= $totalchance) break;
}

echo $item;
?>

Heb ik het even verwisseld die waarde ids, de laatste 2 vooraan en eerste 2 achteraan. De ids die eerst eerst waren en nu achteraan komen nooit meer tevoorschijn. Het is alsof hij maar 2 ids kan pakken ofzo.

[Soultaker]

Ik denk dat je het principe niet helemaal begrepen hebt. Ik zal het nog eens stap voor stap uit proberen te leggen.

Stel dat je drie items hebt, en je wil er één van nemen. Als je een willekeurig getal tussen 0 en 3 genereert, dan kies je het eerste item als het getal in het bereik [0,1) ligt, het tweede item voor het bereik [1,2) en het derde item voor het bereik [1,3). Deze drie gebieden samen lopen van 0 tot 3, daarom genereer je een getal tussen 0 en 3, en omdat ze allemaal even groot zijn heeft elk item een gelijke kans om gekozen te worden.

Als je echter geen gelijke kansen wil, moeten de gebieden een verschillende lengte hebben. Om bijvoorbeeld 50% kans te hebben op het eerste item, 30% op het tweede en 20% op het derde, kun je gebieden indelen als [0, 50), [50, 80), [80, 100). Maar natuurlijk net zo goed [0, 10), [10, 16), [16, 20).

Vervolgens genereer je een getal uniform in het totale bereik en kijk je in welk deelbereik het valt.

Waar je code de mist in gaat, is dat je het hebt over percentages maar ondertussen kansen hebt die samen geen honderd zijn. 65 + 64 + 60 + 45 + 5 = 239, geen 100. Je moet dus of je percentages normaliseren, of (beter) een getal tussen 1 en 239 genereren. Hetzelfde geldt voor het tweede voorbeeld: 30 + 1 + 10 + 80 = 121, geen 100. Het lijkt te werken, maar de kans op het laatste item is in de praktijk gewoon 100 - 30 - 1 -10 = 59 procent, geen 80 procent.

[Verwijderd]

Omg thnx man, ik heb daar helemaal niet aan gedacht!
Echt hartelijk bedankt!!