Reversible shuffle algorithm using a key

by

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?

More Related Contents:

  1. Is using Random and OrderBy a good shuffle algorithm? [closed]
  2. Remove text in-between delimiters in a string (using a regex?)
  3. Split String into smaller Strings by length variable
  4. Compare string similarity
  5. Reversing the given string without using reverse function [closed]
  6. Iterating through a List and .Contains isn’t catching string [closed]
  7. What is the difference between palindrome permutation and permutation? [closed]
  8. Why does Read interfere with ReadLine? [duplicate]
  9. .NET String.Format() to add commas in thousands place for a number
  10. Easiest way to read from and write to files
  11. Easiest way to split a string on newlines in .NET?
  12. Select N random elements from a List in C#
  13. Converting string to title case
  14. Replace Multiple String Elements in C#
  15. String concatenation vs String Builder. Performance
  16. Replacing a char at a given index in string? [duplicate]
  17. Algorithm to find which numbers from a list of size n sum to another number
  18. C++ string::find complexity
  19. Getting hash of a list of strings regardless of order
  20. Finding all combinations of well-formed brackets
  21. Casting vs Converting an object toString, when object really is a string
  22. How to convert a character in to equivalent System.Windows.Input.Key Enum value?
  23. How does StringBuilder work internally in C#?
  24. How to get all the possible 3 letter permutations? [duplicate]
  25. How can I Unescape and Reescape strings in .net?
  26. Why is \ character being doubled in my @ string?
  27. String comparison – strA.ToLower()==strB.ToLower() or strA.Equals(strB,StringComparisonType)?
  28. All cases covered Bresenham’s line-algorithm [closed]
  29. Parsing formatted string
  30. Creating your own Tinyurl style uid

Leave a Comment