A difficult PHP and how select from a weighted array

PHP
1

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

I’m usually the one asking questions around here :eek: 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.


$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.

3

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

if you want to test the code segment I posted for accuracy you can just use this to call the function:

$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: " . (2 / 25) .  "<br />\
";
print "pear: " . ($pear / 1000) . " expected: " . (7 / 25) .  "<br />";
print "pumpkin: " . ($pumpkin  / 1000) . " expected: " . (1 / 25) .  "<br />";
print "peach: " . ($peach / 1000) . " expected: " . (15 / 25) .  "<br />";
5

Here you go:


<?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 > 0 ? array_fill(0, $weight, $fruit[1]) : array();
}

$fruits_array = array(
    array(1, "apple", 0, 0, 1),
    array(2, "pear", 1, 2, 3),
    array(3, "pumpkin", 0, 0, 0),
    array(4, "peach", 5, 9, 0),
);

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

if(!empty($weighted_array)) {
    $weighted_fruit = $weighted_array[rand(0, count($weighted_array))];
    
    echo $weighted_fruit ." was chosen!\
\
";
    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

PHP has a built in array_merge function.

7

You will note that array_flatten uses array_merge in a specific way.

8

Wow Peter, good job, thats some very good code. Kudos :cool:

9

What about this:


// Your fruits
$fruits_array = array();

// Add the fruits
array_push($fruits_array, array( 'name' => 'apple',     'total' => 0,   'values' => array(1, 2, 1)));
array_push($fruits_array, array( 'name' => 'pear',      'total' => 0,   'values' => array(2, 3, 0)));
array_push($fruits_array, array( 'name' => 'pumpkin',   'total' => 0,   'values' => array(3, 4, 1)));
array_push($fruits_array, array( 'name' => 'peach',     'total' => 0,   'values' => array(4, 5, 0)));

// 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

Much simpler I’d say. :smiley:


<?php
$fruits_array = array(
    array(1, "apple", 0, 0, 1),
    array(2, "pear", 1, 2, 3),
    array(3, "pumpkin", 0, 0, 0),
    array(4, "peach", 5, 9, 0),
);

$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
    )
*/