Efficiently Pick N Random Elements from PHP Array (Without Shuffle)

Efficiently pick n random elements from PHP array (without shuffle)

$randomArray = [];
while (count($randomArray) < 5) {
  $randomKey = mt_rand(0, count($array)-1);
  $randomArray[$randomKey] = $array[$randomKey];
}

This will provide exactly 5 elements with no duplicates and very quickly. The keys will be preserved.

Note: You'd have to make sure $array had 5 or more elements or add some sort of check to prevent an endless loop.

How do I select random values from an array in PHP?

$result = array();
foreach( array_rand($my_array, 8) as $k ) {
  $result[] = $my_array[$k];
}

Select 2 random elements from associative array

Grab the keys from the array with array_keys(), shuffle the keys with shuffle(), and print out the values corresponding to the first two keys in the shuffled keys array, like so:

$array = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4);
$keys = array_keys( $array);
shuffle( $keys);
echo $array[ $keys[0] ] . ',' . $array[ $keys[1] ];

Demo

Or, you can use array_rand()'s second parameter to grab two keys, like so:

$array = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4);
$keys = array_rand( $array, 2);
echo $array[ $keys[0] ] . ',' . $array[ $keys[1] ];

Demo

How to get random array values, not just keys with php?

I'd suggest using a different approach, actually. Using array_rand on this array

$chord_amt = array(2,3,4,5,6);

isn't really needed to generate a random number between 2 and 6. PHP has the rand function for that.

Consider the following instead:

// shuffle the list of chords
shuffle($scale);

// take a slice of it with a random length between 2 and 6
$random_chords = array_slice($scale, 0, rand(2, 6));

Randomize a PHP array with a seed?

You can use array_multisort to order the array values by a second array of mt_rand values:

$arr = array(1,2,3,4,5,6);

mt_srand('123');
$order = array_map(create_function('$val', 'return mt_rand();'), range(1, count($arr)));
array_multisort($order, $arr);

var_dump($arr);

Here $order is an array of mt_rand values of the same length as $arr. array_multisort sorts the values of $order and orders the elements of $arr according to the order of the values of $order.

Get a subset of random values from an array php

Well, there are a few alternatives. I'm not sure which is the fastest since you're dealing with a sizable array, but you may want to try them out:

You can use shuffle, which will randomize the entire array. This will likely have the best performance since you're consuming a significant portion of the array (10%).

shuffle($seedkeys);
$result = array_slice($seedkeys, 0, 1000);

You could use array_rand (as you already said) in the manor that Tom Haigh specifies. This will require copying the keys, so if you're dealing with a significant portion of the source array, this may not be the fastest. (Note the use of array_flip, it's needed to allow the usage of array_intersect_key:

$keys = array_flip(array_rand($seedkeys, 1000));
$result = array_intersect_key($seedkeys, $keys);

If memory is tight, the best solution (besides the MySQL one) would be a loop since it doesn't require arrays to be copied at all. Note that this will be slower, but if the array contains a lot of information, it may offset the slowness by being more memory efficient (since it only ever copies exactly what it returns)...

$result = array();
for ($i = 0; $i < 1000; $i++) {
    $result[] = $seedkeys[array_rand($seedkeys)];
}

You could do it in MySQL (assuming that the data for the array starts from MySQL). Be aware this is simple, but not that efficient (See Jan Kneschke's post)...

SELECT * FROM `foo` ORDER BY RAND() LIMIT 1000;

How can I take n elements at random from a Perl array?

The other answers all involve shuffling the array, which is O(n).
It means modifying the original array (destructive) or copying the original array (memory intensive).

The first way to make it more memory efficient is not to shuffle the original array but to shuffle an array of indexes.

# Shuffled list of indexes into @deck
my @shuffled_indexes = shuffle(0..$#deck);

# Get just N of them.
my @pick_indexes = @shuffled_indexes[ 0 .. $num_picks - 1 ];  

# Pick cards from @deck
my @picks = @deck[ @pick_indexes ];

It is at least independent of the content of the @deck, but its still O(nlogn) performance and O(n) memory.

A more efficient algorithm (not necessarily faster, depends on now big your array is) is to look at each element of the array and decide if it's going to make it into the array. This is similar to how you select a random line from a file without reading the whole file into memory, each line has a 1/N chance of being picked where N is the line number. So the first line has a 1/1 chance (it's always picked). The next has a 1/2. Then 1/3 and so on. Each pick will overwrite the previous pick. This results in each line having a 1/total_lines chance.

You can work it out for yourself. A one line file has a 1/1 chance so the first one is always picked. A two line file... the first line has a 1/1 then a 1/2 chance of surviving, which is 1/2, and the second line has a 1/2 chance. For a three line file... the first line has a 1/1 chance of being picked, then a 1/2 * 2/3 chance of surviving which is 2/6 or 1/3. And so on.

The algorithm is O(n) for speed, it iterates through an unordered array once, and does not consume any more memory than is needed to store the picks.

With a little modification, this works for multiple picks. Instead of a 1/$position chance, it's $picks_left / $position. Each time a pick is successful, you decrement $picks_left. You work from the high position to the low one. Unlike before, you don't overwrite.

my $picks_left = $picks;
my $num_left = @$deck;
my @picks;
my $idx = 0;
while($picks_left > 0 ) {  # when we have all our picks, stop
    # random number from 0..$num_left-1
    my $rand = int(rand($num_left));

    # pick successful
    if( $rand < $picks_left ) {
        push @result, $deck->[$idx];
        $picks_left--;
    }

    $num_left--;
    $idx++;
}

This is how perl5i implements its pick method (coming next release).

To understand viscerally why this works, take the example of picking 2 from a 4 element list. Each should have a 1/2 chance of being picked.

1. (2 picks, 4 items):         2/4 = 1/2

Simple enough. Next element has a 1/2 chance that an element will already have been picked, in which case it's chances are 1/3. Otherwise its chances are 2/3. Doing the math...

2. (1 or 2 picks,  3 items):   (1/3 * 1/2) + (2/3 * 1/2) = 3/6 = 1/2

Next has a 1/4 chance that both elements will already be picked (1/2 * 1/2), then it has no chance; 1/2 chance that only one will be picked, then it has 1/2; and the remaining 1/4 that no items will be picked in which case it's 2/2.

3. (0, 1 or 2 picks, 2 items): (0/2 * 1/4) + (1/2 * 2/4) + (2/2 * 1/4) = 2/8 + 1/4 = 1/2

Finally, for the last item, there's a 1/2 the previous took the last pick.

4. (0 or 1 pick, 1 items):     (0/1 * 2/4) + (1/1 * 2/4) = 1/2

Not exactly a proof, but good for convincing yourself it works.

Generate array of random unique numbers in PHP

$max = 5;
$done = false;
while(!$done){
    $numbers = range(0, $max);
    shuffle($numbers);
    $done = true;
    foreach($numbers as $key => $val){
        if($key == $val){
            $done = false;
            break;
        }
    }
}

Most efficient way of randomly choosing a set of distinct integers

For small values of maxValue such that it is reasonable to generate an array of all the integers in memory then you can use a variation of the Fisher-Yates shuffle except only performing the first n steps.

---

If n is much smaller than maxValue and you don't wish to generate the entire array then you can use this algorithm:

1. Keep a sorted list l of number picked so far, initially empty.
2. Pick a random number x between 0 and maxValue - (elements in l)
3. For each number in l if it smaller than or equal to x, add 1 to x
4. Add the adjusted value of x into the sorted list and repeat.

If n is very close to maxValue then you can randomly pick the elements that aren't in the result and then find the complement of that set.

---

Here is another algorithm that is simpler but has potentially unbounded execution time:

1. Keep a set s of element picked so far, initially empty.
2. Pick a number at random between 0 and maxValue.
3. If the number is not in s, add it to s.
4. Go back to step 2 until s has n elements.

In practice if n is small and maxValue is large this will be good enough for most purposes.

---

Related Topics