Reversible Shuffle Algorithm Using a Key

Reversible shuffle algorithm using a key

Look at Fisher-Yates shuffle for a way to permute the string based on a key. Feed the key as the seed into a PRNG, use that to generate the random numbers used by the shuffle.

Now, how to reverse the process? Fisher-Yates works by swapping certain pairs of elements. So to reverse the process you can feed the same key into the same PRNG, then run through the Fisher-Yates algorithm as if you were shuffling an array the size of your string. But actually you don't move anything, just record the indexes of the elements that would be swapped at each stage.

Once you've done this, run through your list of swaps in reverse, applying them to your shuffled string. The result is the original string.

So for example, suppose we've shuffled the string "hello" using the following swaps (I haven't used a PRNG here, I rolled dice, but the point about a PRNG is it gives you the same sequence of numbers given the same seed):

(4,0): "hello" -> "oellh"
(3,3): "oellh" -> "oellh"
(2,1): "oellh" -> "olelh"
(1,0): "olelh" -> "loelh"

So, the shuffled string is "loelh".

To deshuffle, I generate the same series of "random" numbers, 0, 3, 1, 0. Then apply the swaps in reverse order:

(1,0): "loelh" -> "olelh"
(2,1): "olelh" -> "oellh"
(3,3): "oellh" -> "oellh"
(4,0): "oellh" -> "hello"

Success!

The downside of this of course is that it uses a lot of memory for the deshuffle: an array of indexes as long as your original array of chars. So for truly huge arrays, you might want to choose a PRNG (or anyway a sequence-generation function) that can be stepped either forwards or backwards without having to store all the output. This rules out hash-based cryptographically secure PRNGs, but LFSRs are reversible.

Btw, why do you want to do this?

reverse deterministic shuffle - derive key

Shuffling is just creating a random permutation of a given sequence. The typical way to do that is something like the Fisher-Yates Shuffle that you pointed out. The problem is that the shuffle program generates multiple random numbers based on a seed, and unless you implement the random number generator there's no easy way to reverse the sequence of random numbers.

There is another way to do it. What if you could generate the nth permutation of a sequence directly? That is, given the string "Fast", you define the first few permutations as:

0  Fast
1  Fats
2  Fsat
3  Fsta
... etc. for all 24 permutations

You want a random permutation of those four characters. Select a random number from 0 to 23 and then call a function to generate that permutation.

If you know the key, you can call a different function, again passing that key, to have it reverse the permutation back to the original.

In the fourth article in his series on permutations, Eric Lippert showed how to generate the nth permutation without having to generate all of the permutations that come before it. He doesn't show how to reverse the process, but doing so shouldn't be difficult if you understand how the generator works. It's well worth the time to study the entire series of articles.

If you don't know what the key (i.e. the random number used) is, then deriving the sequence of swaps required to get to the original order is expensive.

Edit

Upon reflection, it just might be possible to derive the key if you're given the original sequence and the transformed sequence. Since you know how far each symbol has moved, you should be able to derive the key. Consider the possible permutations of two letters:

0. ab  1. ba

Now, assign the letter b the value of 0, and the letter a the value of 1. What permutation number is ba? Find a in the string, swap to the left until it gets to the proper position, and multiply the number of swaps by one.

That's too easy. Consider the next one:

0. abc  1. acb  2. bac
3. cab  4. bca  5. cba

a is now 2, b is 1, and c is 0. Given cab:

swap a left one space. 1x2 = 2. Result is `acb`
swap b left one space. 1x1 = 1. Result is `abc`

So cab is permutation #3.

This does assume that your permutation generator numbers the permutations in the same way. It's also not a terribly efficient way of doing things. Worst case will require n(n-1)/2 swaps. You can optimize the swaps by moving things in an array, but it's still an O(n^2) algorithm. Where n is the length of the sequence. Not terrible for 100 or maybe even 1,000 items. Pretty bad after that, though.

Arraylist Shuffle algorithm using a key

    private class myItem
    {
        public Int32 ID { get; set; }
        public Int32 Rand { get; set; }
        public String Value { get; set; }

    }

    private void Main(object sender, EventArgs e)
    {

        string[] array = new string[] { "alpha", "beta", "gamma", "delta" };
        List<myItem> myArray = addKeys(array);//adds keys to array required for randomization and reversing
        string[] randomarray = randomize(myArray);
        string[] reversedarray = reverse(myArray);

    }
    private List<myItem> addKeys(string[] array)
    {
        Random random = new Random();
        List<myItem> myArr = new List<myItem>();
        for (int i = 0; i < array.Length; i++)
        {
            myArr.Add(new myItem { ID = i, Rand = random.Next(), Value = array[i] });

        }
        return myArr;
    }
    private string[] randomize(List<myItem> myArray)
    {
        return (from item in myArray
                         orderby item.Rand
                         select item.Value).ToArray();
    }
    private string[] reverse(List<myItem> myArray)
    {
        return (from item in myArray
                         orderby item.ID
                         select item.Value).ToArray();
    }

Arraylist Shuffle algorithm using a key

    private class myItem
    {
        public Int32 ID { get; set; }
        public Int32 Rand { get; set; }
        public String Value { get; set; }

    }

    private void Main(object sender, EventArgs e)
    {

        string[] array = new string[] { "alpha", "beta", "gamma", "delta" };
        List<myItem> myArray = addKeys(array);//adds keys to array required for randomization and reversing
        string[] randomarray = randomize(myArray);
        string[] reversedarray = reverse(myArray);

    }
    private List<myItem> addKeys(string[] array)
    {
        Random random = new Random();
        List<myItem> myArr = new List<myItem>();
        for (int i = 0; i < array.Length; i++)
        {
            myArr.Add(new myItem { ID = i, Rand = random.Next(), Value = array[i] });

        }
        return myArr;
    }
    private string[] randomize(List<myItem> myArray)
    {
        return (from item in myArray
                         orderby item.Rand
                         select item.Value).ToArray();
    }
    private string[] reverse(List<myItem> myArray)
    {
        return (from item in myArray
                         orderby item.ID
                         select item.Value).ToArray();
    }

Can a seeded shuffle be reversed?

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.

Unshuffle an array of int/char

I suggest following algorithm

• Generate a vector indices with std::iota of st.size() elements.
• Shuffle that vector with the same engine with the same seed.
• While looping over the shuffled vector, generate a new string result where result[indices[i]] = st[i]

---

Related Topics