How can I gradually make an array sparser?

Question

I have a fully-populated array of values, and I would like to arbitrarily remove elements from this array with more removed towards the far end.

For example, given input ( where a . signifies a populated index )

............................................

I would like something like

....... . ...  .. .  .  ..    .          .  

My first thought was to count the elements, then iterate over the array generating a random number somewhere between the current index and the total size of the array, eg:

if ( mt_rand( 0, $total ) > $total - $current_index ) 
    //remove this element

however, as this entails making a random number each time the loop goes round it becomes very arduous.

Is there a better way of doing this?

Answer 1

One easy way is to flip a weighted coin for each entry with coin flips more weighted towards the end. For example, if the array is size n, for each entry you could choose a random number from 0 to n-1 and only keep the value if the index is less than or equal to the random number. (That is, keep each entry with probability 1 - index/total.) This has the nice advantage that if you're going to be compacting your array anyways, and you're using a good enough but efficient random number generator (could be a simple integer hash over a nonce), it's going to be rather fast for memory access.

On the other hand if you're only blanking out a few items and aren't rearranging the array, you can go with some sort of weighted random number generator that more often chooses numbers that are toward the end of the index. For example, if you have a random number generator that generates floats in the value of [0,1] (closed or open bounds not mattering that much likely), consider obtaining such a random float r and squaring it. This will tend to prefer lower values. You can fix this by flipping it around: 1-r^2. Of course, you need this to be in your index range of 0 to n - 1, so take floor(n * (1 - r^2)) and also round n down to n-1.

There's practically an infinite number of variations on both of these techniques.

Answer 2

This is quite probably not the best/most efficient way to do this, but it is the best I can come up with and it does work.

N.B. the codepad example takes a long time to execute, but this is because of the pretty-print loop I added to the end so you can see it visibly working. If you remove the inner loop, execution time drops to acceptable levels.

<?php

  $array = range(0, 99);

  for ($i = 0, $count = count($array); $i < $count; $i++) {

    // Get array keys
    $keys = array_keys($array);

    // Get a random number between 0 and count($keys) - 1
    $rand = mt_rand(0, count($keys) - 1);

    // Cut $rand elements off the beginning of the keys
    $keys = array_slice($keys, $rand);

    // Unset a random key from the remaining keys
    unset($array[$keys[array_rand($keys)]]);

  }