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

回答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.