shuffle an array with a "limit" in PHP

Question

What I try to achieve: randomize the order of all elements in an array, but allow each element to change its position only by a limited number of "steps".

Say I have an array like below, and I wish to randomize with a limit of 2 steps:

$array = [92,12,2,18,17,88,56];

An outcome could be: [2,12,92,17,18,56,88] (all elements of the array moved a maximum of 2 steps), but it could not be: [56,92,2,12,17,18,88] because in this example 56 moved too far.

I considered using a combination of array_chunk and shuffle, but this is problematic because elements will be shuffled inside their chunk, resulting in elements at the beginning or end of a chunk only moving in one direction. This is what I came up with (and problematic):

// in chunks of 3 an element can move a max. of 2 steps.
$chunks = array_chunk($array, 3); 
$newChunks = [];

foreach ($chunks as $chunk){
    $keys = array_keys($chunk);
    shuffle($keys);

    $newChunk = [];
    foreach ($keys as $key){
        $newChunk[$key] = $chunk[$key];
    }

    $newChunks[] = $newChunk;
}

Another idea I had was to get the key of the item in the array and with rand add of subtract my limit. For example:

foreach ( $array as $key => $value ) {
    $newArray[] = ["key" => $key+rand(-2,2), "value" => $value];
};

This creates a new array with each of its elements being an array with the original value plus a value key that is the original key plus or minus 2. I could flatten this array, but the problem with this is that I can have duplicate keys.

Answer 1

I created this function to do this, but I guess it needs more improvements:

/**
 * @param array $array
 * @param int $limit
 * @return array
 */
function shuffleArray(array $array, int $limit): array
{
    $arrayCount = count($array);
    $limit = min($arrayCount, $limit);
    for ($i = 0; $i < $limit; $i++) {
        for ($j = 0; $j < $arrayCount;) {
            $toIndex = min($arrayCount - 1, $j + rand(0, 1));
            [$array[$j], $array[$toIndex]] = [$array[$toIndex], $array[$j]];
            $j += (($toIndex === $j) ? 1 : 2);
        }
    }

    return $array;
}

Test:

$array = [92, 12, 2, 18, 17, 88, 56];
$limit = 2;
$result = shuffleArray($array, $limit); // [12, 92, 17, 2, 18, 56, 88]

Answer 2

Here is a possible solution in one pass :

Try to swap each element at position i with an element between i (stay in place) and i+x. I look only forward to avoid swaping an element several times. And I need an extra array to flag the already swapped elements. I don't need to process them in the future as they were already moved.

function shuffle_array($a, $limit)
{
    $result = $a ;
    $shuffled_index = array() ; // list of already shuffled elements

    $n = count($result);
    for($i = 0 ; $i < $n ; ++$i)
    {
        if( in_array($i, $shuffled_index) ) continue ; // already shuffled, go to the next elements

        $possibleIndex = array_diff( range($i, min($i + $limit, $n-1)), $shuffled_index) ; // get all the possible "jumps", minus the already- shuffled index
        $selectedIndex = $possibleIndex[ array_rand($possibleIndex) ]; // randomly choose one of the possible index

        // swap the two elements
        $tmp = $result[$i] ;
        $result[$i] = $result[$selectedIndex] ;
        $result[$selectedIndex] = $tmp ;

        // element at position $selectedIndex is already shuffled, it needs no more processing
        $shuffled_index[] = $selectedIndex ; 
    }

    return $result ;
}

$array = [92,12,2,18,17,88,56];
$limit = 2 ;

shuffle_array($array, $limit); // [2, 18, 92, 12, 17, 56, 88]

I expect more elements to stay in place than in the solution of Kerkouch, as some elements can have very few remaining free choices.