How to control the probability of random selection

问题:

I want to select a user from a user list randomly, but I want the VIP users have higher probability to be selected, how to implement such a algorithm?

Sample data:

$users = array(
    array('name'=>'user1', 'is_vip'=>false),
    array('name'=>'user2', 'is_vip'=>false),
    array('name'=>'user3', 'is_vip'=>false),
    array('name'=>'user4', 'is_vip'=>false),
    array('name'=>'user5', 'is_vip'=>false),
    array('name'=>'user6', 'is_vip'=>true),
    array('name'=>'user7', 'is_vip'=>false),
    array('name'=>'user8', 'is_vip'=>false),
    array('name'=>'user8', 'is_vip'=>true),
    array('name'=>'user10', 'is_vip'=>true),
    array('name'=>'user11', 'is_vip'=>false),
    array('name'=>'user12', 'is_vip'=>false),
);

回答1:

You can solve this problem by sampling from a discrete distribution. Assign each of the different users a weight based on whether or not they are a VIP, then use a weighted random sampling algorithm to choose them randomly, but with a bias toward VIP users.

There are a bunch of algorithms for this and many of them are fast and easy to code up. There's a detailed write up available online that details many of them.

Hope this helps!

回答2:

This most likely is not the 'correct' way to do it, but you could split them up:

foreach($users as $spUsers){
    if($spUsers['is_vip']==true){
        $splitUsers[0][]=array('name'=>$spUsers['name'],'is_vip'=>$spUsers['is_vip']);
    } else {
        $splitUsers[1][]=array('name'=>$spUsers['name'],'is_vip'=>$spUsers['is_vip']);
    }
}

function weightedrand($min, $max, $gamma) {
    $offset= $max-$min+1;
    return floor($min+pow(lcg_value(), $gamma)*$offset);
}

gamma 1 is unweighted, lower gives more of the higher numbers and vice versa

$array_to_pick_from = weightedrand(0, 1, .5);

$array_to_pick_from will have an array to pick a random user from.

Like I said this is probably not at all the best way to do it. But it should do the trick until someone much smarter then me rolls around.

I got the weighted random from this answer: Generating random results by weight in PHP?