Can a seeded shuffle be reversed?

Question

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.)

Answer 1

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.