Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can a seeded shuffle be reversed?

Take this function, which is a seeded Fisher-Yates shuffle (the order is random, but reproducible given the same seed):

function seeded_shuffle(array &$items, $seed = false) {
    $items = array_values($items);
    mt_srand($seed ? $seed : time());
    for ($i = count($items) - 1; $i > 0; $i--) {
        $j = mt_rand(0, $i);
        list($items[$i], $items[$j]) = array($items[$j], $items[$i]);
    }
}

Can this algorithm be reversed? I.e., given the seed value and the shuffled array, can the array be "unshuffled" into its original order? If so, how?

(The question came up in the comments here.)

like image 821
deceze Avatar asked Mar 19 '23 07:03

deceze


1 Answers

Turns out the answer is yes, and pretty simple:

function seeded_unshuffle(array &$items, $seed) {
    $items = array_values($items);

    mt_srand($seed);
    $indices = [];
    for ($i = count($items) - 1; $i > 0; $i--) {
        $indices[$i] = mt_rand(0, $i);
    }

    foreach (array_reverse($indices, true) as $i => $j) {
        list($items[$i], $items[$j]) = [$items[$j], $items[$i]];
    }
}

Just generate the same random number sequence using the known seed, and traverse it in reverse.

like image 180
deceze Avatar answered Mar 28 '23 01:03

deceze