Reverse an array.shuffle(random) to get the original?

Question

I would like to know if there's a way to make a reverse of the function array.shuffle(random(seed)) on Ruby? Example:

array = [1, 2, 3, 4, 5]
array.shuffle!(random: Random.new(seed))
# => [5, 3, 2, 1, 4]

It's possible to get the original array using the same seed? Thanks a lot

Answer 1

Based on Kent Dahl's answer, I came up with the following solution:

class Array
  def unshuffle(random:)
    transformed_order = (0...length).to_a.shuffle!(random: random)
    sort_by.with_index{|_, i| transformed_order[i]}
  end
end

SEED = 42

# Random array of numbers from 1 to 10
original_array = (1..10).map{ rand 1..10 }

shuffled = original_array.shuffle(random: Random.new(SEED))
unshuffled = shuffled.unshuffle(random: Random.new(SEED))

puts "Original:   #{original_array}"
puts "Shuffled:   #{shuffled}"
puts "Unshuffled: #{unshuffled}"

puts unshuffled == original_array

Sample output:

Original:   [2, 3, 7, 3, 7, 2, 5, 8, 6, 2]
Shuffled:   [6, 3, 2, 2, 8, 7, 2, 7, 3, 5]
Unshuffled: [2, 3, 7, 3, 7, 2, 5, 8, 6, 2]
true

Basically, it works by shuffling a new sorted array using the same seed the original array was shuffled with, then observing the final shuffled positions of the sorted array and using that information to reverse the shuffling of the original array.

This solution should be robust against differences in the implementation of the shuffle method and Random class across different versions and implementations of Ruby.

Answer 2

While there is no unshuffle method AFAIK, it isn't impossible. However, you might need to dig into the implementation of Array#shuffle to do it, which means it might not work across Ruby versions and different platforms.

Since PRNGs are deterministic and you have the seed, running a new shuffle on another array with the same size and same seed should give the exact same reshuffling order.

Which means you could shuffle an array of indexes and use the result to reverse map your shuffled array of actual values or elements.

Answer 3

You can't undo randomness, but you can leave a trail of crumbs to help you get back to where you were before:

foo = ('a' .. 'g').to_a
foo.map!.with_index{ |f, i| [f, i] }.shuffle!
foo # => [["g", 6], ["a", 0], ["d", 3], ["f", 5], ["b", 1], ["c", 2], ["e", 4]]

foo.sort_by!{ |f, i| i }.map!{ |f, i| f }
foo # => ["a", "b", "c", "d", "e", "f", "g"]

Or you can simply keep a copy of your original array, or work from a copy of it:

foo = ('a' .. 'g').to_a
bar = foo.shuffle

foo # => ["a", "b", "c", "d", "e", "f", "g"]
bar # => ["b", "c", "d", "f", "a", "g", "e"]

foo.object_id # => 70308031906280
bar.object_id # => 70308031906080

object_id lets us see whether the arrays are separate objects, which is important because of how Ruby works.

Keeping a duplicate of it around:

foo = ('a' .. 'g').to_a
bar = foo.dup
foo.shuffle!
foo # => ["g", "b", "f", "c", "d", "e", "a"]
bar # => ["a", "b", "c", "d", "e", "f", "g"]
foo.object_id # => 70123956309980
bar.object_id # => 70123956307920

foo = bar
foo.object_id # => 70123956307920
bar.object_id # => 70123956307920

Or:

foo = bar.dup
foo.object_id # => 70123960710260
bar.object_id # => 70123956307920

Answer 4

There is no way to get the original array back. If you have the array which is sorted already then you can get it back by using sort. And also when you use shuffle, it means you want to change the order. You can store the original array before shuffling, if you want to use it.

Answer 5

Kent Dahl's Idea in c#

        public void Shuffle<T>(this T[] array, int seed)
        {
            var rnd = new Random(seed);
            int n = array.Length;
            while (n > 1)
            {
                int swappableIndex = rnd.Next(n--);
                T temp = array[n];
                array[n] = array[swappableIndex];
                array[swappableIndex] = temp;
            }
        }
        public void Unshuffle<T>(this T[] array, int seed)
        {
            var rnd = new Random(seed);
            int n = array.Length;
            int[] rSequence = new int[n - 1];
            for (int i = 0; i < array.Length - 1; i++)
            {
                rSequence[i] = rnd.Next(n--);
            }
            for (int i = 1; i < array.Length; i++)
            {
                int swappableIndex = rSequence[^i];
                T temp = array[i];
                array[i] = array[swappableIndex];
                array[swappableIndex] = temp;
            }
        }

Usage

            Console.WriteLine("Original");
            var array = new int[] { 1, 5, 6, 8, 23, 56, 98, 456, 255, 266, 666, 666, 2, 4, 9 };
            Console.WriteLine(string.Join(',', array.Select(x => x.ToString())));

            Console.WriteLine("Shuffled");
            array.Shuffle<int>(25);
            Console.WriteLine(string.Join(',', array.Select(x => x.ToString())));

            Console.WriteLine("Reshuffled");
            array.Unshuffle<int>(25);
            Console.WriteLine(string.Join(',', array.Select(x => x.ToString())));

Note : Ensure that the seed value you given to create PRNG should be equal while shuffling and unshuffling(I don't know if the word exists though) the same array