CODEWITHSUNDEEP
phparrayssortingrandomshuffle
user999489
user999489

Reputation:

How to do a special shuffle function in php

I need a function that randomizes an array similar to what shuffle does, with the difference that each element has different chances.

For example, consider the following array:

$animals = array('elephant', 'dog', 'cat', 'mouse');

elephant has an higher chance of getting on the first index than dog. Dog has an higher chance than cat and so on. For example, in this particular example elephant could have a chance of 40% in getting in the 1st position, 30% of getting on the 2nd position, 20% on getting on 3rd and 10% getting on last.

So, after the shuffling, the first elements in the original array will be more likely (but not for sure) to be in the first positions and the last ones in the last positions.

Upvotes: 2

Views: 482

Answers (3)

kirilloid
kirilloid

Reputation: 14304

Normal shuffle may be implemented just as

  • dropping items randomly at some range
  • picking them up from left to right

We can adjust dropping step, drop every element not into whole range, but at some sliding window. Let N would be amount of elements in array, window width would be w and we'll move it at each step by off. Then off*(N-1) + w would be total width of the range.

Here's a function, which distorts elements' positions, but not completely at random.

function weak_shuffle($a, $strength) {
    $len = count($a);
    if ($len <= 1) return $a;
    $out = array();
    $M = mt_getrandmax();
    $w = round($M / ($strength + 1)); // width of the sliding window
    $off = ($M - $w) / ($len - 1); // offset of that window for each step.
    for ($i = 0; $i < $len; $i++) {
        do {
            $idx = intval($off * $i + mt_rand(0, $w));
        } while(array_key_exists($idx, $out));
        $out[$idx] = $a[$i];
    }
    ksort($out);
    return array_values($out);
}
  • $strength = 0 ~normal shuffle.
  • $strength = 0.25 ~your desired result (40.5%, 25.5%, 22%, 12% for elephant)
  • $strength = 1 first item will never be after last one.
  • $strength >= 3 array is actually never shuffled

Playground for testing:

$animals = array( 'elephant', 'dog', 'cat', 'mouse' );
$pos = array(0,0,0,0);
for ($iter = 0; $iter < 100000; $iter++) {
    $shuffled = weak_shuffle($animals, 0.25);
    $idx = array_search('elephant', $shuffled);
    $pos[$idx]++;
}
print_r($pos);

Upvotes: 4

Lajos Arpad
Lajos Arpad

Reputation: 76434

You have an array, let's say of n elements. The probability that the i'th element will go to the j'th position is P(i, j). If I understood well, the following formula holds:

(P(i1, j1) >= P(i2, j2)) <=> (|i1 - j1| <= |j1 - i1|)

Thus, you have a Galois connection between the distance in your array and the shuffle probability. You can use this Galois connection to implement your exact formula if you have one. If you don't have a formula, you can invent one, which will meet the criteria specified above. Good luck.

Upvotes: 1

Vitaly Muminov
Vitaly Muminov

Reputation: 1952

Try to use this algorithm:

$animals  = [ 'elephant', 'dog', 'cat', 'mouse' ]; // you can add more animals here
$shuffled = [];

$count = count($animals);

foreach($animals as $chance => $animal) {
    $priority = ceil(($count - $chance) * 100 / $count);
    $shuffled = array_merge($shuffled, array_fill(0, $priority, $animal));
}

shuffle($shuffled);
$animals = array_unique($shuffled);

Upvotes: 2

Related Questions