SitePoint Sponsor

User Tag List

Results 1 to 10 of 10
  1. #1
    SitePoint Zealot sifuhall's Avatar
    Join Date
    Jun 2001
    Location
    out of the sidehatch
    Posts
    135
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    A difficult PHP and how select from a weighted array

    This may be a bizarre questions so please let me know if I can help clarify anything.

    I have an array that contains an id, a name, and 3 values.

    Similar to this:

    1, apple, 0, 0, 1
    2, pear, 1, 2, 3
    3, pumpkin, 0, 0, 0
    4, peach, 5, 9, 0

    I need to select a random fruit (apple, pear, pumpkin, or peach) but the selection should be based on the values afterwards.

    I.E. apple has 0 + 0 + 1 for a total of 1.
    pear has 1 + 2 + 3 for a total of 6.
    pumpkin has 0 + 0 + 0 for a total of 0.
    peach has 5 + 9 + 0 for a total of 14.

    Every fruit should have at least a small chance of being selected so to be safe I add 1 to all the values so I now have a list like this:
    apple: 2
    pear: 7
    pumpkin: 1
    peach: 15

    So now I create a list like this:

    apple
    apple
    pear
    pear
    pear
    pear
    pear
    pear
    pear
    pumpkin
    peach
    peach
    peach
    peach
    peach
    peach
    peach
    peach
    peach
    peach
    peach
    peach
    peach
    peach
    peach

    And with this list I select 1 random entry.

    This allows the fruit with the higher values to be selected more often, but every one has at least a slight chance of being selected.

    Now, there absolutely must be a better was of performing this and still keep the same base chance for selection.

    Please help.

    How can I do this better?

  2. #2
    SitePoint Addict
    Join Date
    May 2008
    Location
    Missouri, USA
    Posts
    273
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I'm usually the one asking questions around here but I thought I'd give this a try for fun. One way is to do it is as you describe and list out all the possibilities in a temporary array. Or I chose to do it using just numbers.

    PHP Code:
    $fruits = array();

    array_push($fruits, array('apple',0,0,1));
    array_push($fruits, array('pear',1,2,3));
    array_push($fruits, array('pumpkin',0,0,0));
    array_push($fruits, array('peach',5,9,0));

    $result getRand($fruits);

    print 
    $result;

    function 
    getRand($fruits){

    $fruitTotal = array();
    $grandTotal 0;
    $randTotal 0;
        
        
    //Calculate the total weight for each fruit
        
    foreach($fruits as $fruit){
        
            
    //Add 1 to ensure that every fruit has at least a small chance
            
    $total $fruit[1] + $fruit[2] + $fruit[3] + 1;

            
    array_push($fruitTotal, array($fruit[0], $total));
            
    $grandTotal += $total;
        }

        
    $rand rand(1,$grandTotal);

        
    //The random value above will fall within one of the fruit 
        //number ranges calculated in the first part of the function
        
    foreach($fruitTotal as $fruit){
            
    $randTotal += $fruit[1];
            
            if(
    $randTotal >= $rand){
                return 
    $fruit[0];
            }
        }

        return 
    "Selection Failed";

    I'm also open to any suggestions on ways to improve this as I'm sure it is not perfectly efficient.
    Follow Me On Twitter: BryceRay

  3. #3
    SitePoint Wizard Darren884's Avatar
    Join Date
    Aug 2003
    Location
    Southern California, United States
    Posts
    1,616
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Heres my theory, not my code. What I would do is count the total number so for that there would be 22 (because you wanted each to have at least 1). Then I would start assigning each fruit a range (first fruit the number start would be 1) with the ending number the sum of the 3 numbers mentioned and the fruits after that the starting range number would be the previous range's number + 1 and that would be added to the ranges end number vise versa. Then I would do a rand(1, 22) and which ever range the selected number was in would be chosen. Perhaps there is a way to do this with SQL but I don't know off the top of my head.

    Example:
    apple 1+1+1 = 3 $apple = range(1, 3);
    pear 2+2+2 = 6 $pear = range(4, 9);
    pumpkin 3+3+3 = 9 $pumpkin = range(10, 18)
    peach 4+4+4 = 12 $peach = range(19, 30);

    $selection = rand(1, 30);

    Then use in_array to find the one with the selected number. There probably is a shorter way to conduct it but like I said I don't know off the top of my head right now at night.

  4. #4
    SitePoint Addict
    Join Date
    May 2008
    Location
    Missouri, USA
    Posts
    273
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    if you want to test the code segment I posted for accuracy you can just use this to call the function:

    PHP Code:
    $test = array();
    for(
    $i=0;$i<1000;$i++){
    $result getRand($fruits);
    array_push($test,$result);
    }

    $apple 0;
    $pear 0;
    $pumpkin 0;
    $peach 0;
    foreach(
    $test as $var){
        if(
    $var == 'apple'$apple++;
        elseif(
    $var == 'pear'$pear++;
        elseif(
    $var == 'pumpkin'$pumpkin++;
        else 
    $peach++;
    }

    print 
    "apple: " . ($apple 1000) . " expected: " . (25) .  "<br />\n";
    print 
    "pear: " . ($pear 1000) . " expected: " . (25) .  "<br />";
    print 
    "pumpkin: " . ($pumpkin  1000) . " expected: " . (25) .  "<br />";
    print 
    "peach: " . ($peach 1000) . " expected: " . (15 25) .  "<br />"
    Follow Me On Twitter: BryceRay

  5. #5
    SitePoint Zealot
    Join Date
    May 2008
    Location
    Montreal
    Posts
    155
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Here you go:

    PHP Code:
    <?php

    /**
     * Flatten a two-dimensional array into a 1-dimensional array.
     */
    function array_flatten(array $arr) {
        if(empty(
    $arr)) { return $arr; }
        return 
    call_user_func_array("array_merge"$arr);
    }

    function 
    weight_fruit($fruit) {
        
    $weight $fruit[2] + $fruit[3] + $fruit[4];
        return 
    $weight array_fill(0$weight$fruit[1]) : array();
    }

    $fruits_array = array(
        array(
    1"apple"001),
        array(
    2"pear"123),
        array(
    3"pumpkin"000),
        array(
    4"peach"590),
    );

    $weighted_array array_flatten(array_map("weight_fruit"$fruits_array));

    if(!empty(
    $weighted_array)) {
        
    $weighted_fruit $weighted_array[rand(0count($weighted_array))];
        
        echo 
    $weighted_fruit ." was chosen!\n\n";
        
    print_r($weighted_array);
    }
    Example run here: http://codepad.org/fF9KclEm

    This example can be made shorter with PHP 5.3 by making "weight_fruit" an anonymous function passed into array_map.

    Also, you get this nice array_flatten for free! I leave figuring out why that works so nicely as an exercise to the reader.

  6. #6
    From space with love silver trophy
    SpacePhoenix's Avatar
    Join Date
    May 2007
    Location
    Poole, UK
    Posts
    4,995
    Mentioned
    100 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by Peter Goodman View Post
    Here you go:

    PHP Code:
    <?php

    /**
     * Flatten a two-dimensional array into a 1-dimensional array.
     */
    function array_flatten(array $arr) {
        if(empty(
    $arr)) { return $arr; }
        return 
    call_user_func_array("array_merge"$arr);
    }

    function 
    weight_fruit($fruit) {
        
    $weight $fruit[2] + $fruit[3] + $fruit[4];
        return 
    $weight array_fill(0$weight$fruit[1]) : array();
    }

    $fruits_array = array(
        array(
    1"apple"001),
        array(
    2"pear"123),
        array(
    3"pumpkin"000),
        array(
    4"peach"590),
    );

    $weighted_array array_flatten(array_map("weight_fruit"$fruits_array));

    if(!empty(
    $weighted_array)) {
        
    $weighted_fruit $weighted_array[rand(0count($weighted_array))];
        
        echo 
    $weighted_fruit ." was chosen!\n\n";
        
    print_r($weighted_array);
    }
    Example run here: http://codepad.org/fF9KclEm

    This example can be made shorter with PHP 5.3 by making "weight_fruit" an anonymous function passed into array_map.

    Also, you get this nice array_flatten for free! I leave figuring out why that works so nicely as an exercise to the reader.
    PHP has a built in array_merge function.
    Community Team Advisor
    Forum Guidelines: Posting FAQ Signatures FAQ Self Promotion FAQ
    Help the Mods: What's Fluff? Report Fluff/Spam to a Moderator

  7. #7
    SitePoint Zealot
    Join Date
    May 2008
    Location
    Montreal
    Posts
    155
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by SpacePhoenix View Post
    PHP has a built in array_merge function.
    You will note that array_flatten uses array_merge in a specific way.

  8. #8
    SitePoint Wizard Darren884's Avatar
    Join Date
    Aug 2003
    Location
    Southern California, United States
    Posts
    1,616
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Wow Peter, good job, thats some very good code. Kudos

    Quote Originally Posted by Peter Goodman View Post
    Here you go:

    PHP Code:
    <?php

    /**
     * Flatten a two-dimensional array into a 1-dimensional array.
     */
    function array_flatten(array $arr) {
        if(empty(
    $arr)) { return $arr; }
        return 
    call_user_func_array("array_merge"$arr);
    }

    function 
    weight_fruit($fruit) {
        
    $weight $fruit[2] + $fruit[3] + $fruit[4];
        return 
    $weight array_fill(0$weight$fruit[1]) : array();
    }

    $fruits_array = array(
        array(
    1"apple"001),
        array(
    2"pear"123),
        array(
    3"pumpkin"000),
        array(
    4"peach"590),
    );

    $weighted_array array_flatten(array_map("weight_fruit"$fruits_array));

    if(!empty(
    $weighted_array)) {
        
    $weighted_fruit $weighted_array[rand(0count($weighted_array))];
        
        echo 
    $weighted_fruit ." was chosen!\n\n";
        
    print_r($weighted_array);
    }
    Example run here: http://codepad.org/fF9KclEm

    This example can be made shorter with PHP 5.3 by making "weight_fruit" an anonymous function passed into array_map.

    Also, you get this nice array_flatten for free! I leave figuring out why that works so nicely as an exercise to the reader.
    Have a good day.

  9. #9
    SitePoint Guru
    Join Date
    Jun 2006
    Posts
    638
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    What about this:
    PHP Code:
    // Your fruits
    $fruits_array = array();

    // Add the fruits
    array_push($fruits_array, array( 'name' => 'apple',     'total' => 0,   'values' => array(121)));
    array_push($fruits_array, array( 'name' => 'pear',      'total' => 0,   'values' => array(230)));
    array_push($fruits_array, array( 'name' => 'pumpkin',   'total' => 0,   'values' => array(341)));
    array_push($fruits_array, array( 'name' => 'peach',     'total' => 0,   'values' => array(450)));

    // Set weights
    $total 0;
    foreach (
    $fruits_array as $key => $value) {
      
    $fruits_array[$key]['total'] = array_sum($value['values']);
      
    $total += $fruits_array[$key]['total'];
    }

    // Get a random fruit based on weight
    $rand rand(0,$total);

    // See what fruit you got
    $fruit null;
    $total 0;
    foreach (
    $fruits_array as $key => $value) {
      
    $total += $value['total'];
      if  (
    $rand <= $total) {
        
    $fruit $fruits_array[$key];
        break;
      }
    }

    // This is your fruit
    print_r($fruit); 
    In case you need to add more weights than the three.
    You can also cache the "Set weights" section, and update it only when your wights change.
    That way, you save allot of CPU.

  10. #10
    Twitter: @AnthonySterling silver trophy AnthonySterling's Avatar
    Join Date
    Apr 2008
    Location
    North-East, UK.
    Posts
    6,111
    Mentioned
    3 Post(s)
    Tagged
    0 Thread(s)
    Much simpler I'd say.
    PHP Code:
    <?php
    $fruits_array 
    = array(
        array(
    1"apple"001),
        array(
    2"pear"123),
        array(
    3"pumpkin"000),
        array(
    4"peach"590),
    );

    $weighted = array();

    foreach(
    $fruits_array as $fruit){
        
    $weighted $weighted + (array)array_fill(
            
    count($weighted),
            (
    $fruit[2] + $fruit[3] + $fruit[4] + 3),
            
    $fruit[1]
        );
    }

    print_r($weighted);

    /*
        Array
        (
            [0] => apple
            [1] => apple
            [2] => apple
            [3] => apple
            [4] => pear
            [5] => pear
            [6] => pear
            [7] => pear
            [8] => pear
            [9] => pear
            [10] => pear
            [11] => pear
            [12] => pear
            [13] => pumpkin
            [14] => pumpkin
            [15] => pumpkin
            [16] => peach
            [17] => peach
            [18] => peach
            [19] => peach
            [20] => peach
            [21] => peach
            [22] => peach
            [23] => peach
            [24] => peach
            [25] => peach
            [26] => peach
            [27] => peach
            [28] => peach
            [29] => peach
            [30] => peach
            [31] => peach
            [32] => peach
        )
    */
    @AnthonySterling: I'm a PHP developer, a consultant for oopnorth.com and the organiser of @phpne, a PHP User Group covering the North-East of England.


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •