Unshuffle an array of int/char

Question

To shuffle the chars of the string st, I use std::shuffle and a random number generator, which is fed by a known seed. This is part of an encoder that, for simplicity, just shuffles the input.

The shuffled data is going to be sent to a decoder. At that side we don't have access to the original input, but the shuffled one.

How can I Unshuffle the string shuffledSt, using the same random number generator and the same seed, until I can obtain the original string st?

#include <random>
#include <algorithm>
int main (int argc, char* argv[])
{
    std::string st = "asdfgh";
    int seed = 1000;
    
    std::shuffle(st.begin(), st.end(), std::default_random_engine(seed));
    std::cerr << st << '\n';

    std::string shuffledSt = st;

    return 0;
}

"Unshuffle"? Do you mean "sort", or do you mean "magically restore the original string, no matter what it looked like"? Or is the actual problem that you really want a shuffled _copy_ of `st` rather than modifying it? — You, Jun 08 '17 at 14:27
`default_random_engine` is implementation defined, so you cannot do so portably. **If** you knew which type of random engine it was using, and if it were invertable (for example a linear congruent generator) then you could implement an "unshuffle" but you'd also need to know the implementation of `std::shuffle` to try to invert that process too. So long story short, probably not possible. — Cory Kramer, Jun 08 '17 at 14:28
I don't believe [`std::shuffle`](http://en.cppreference.com/w/cpp/algorithm/random_shuffle) is easily reversible. Any solution will likely be implementation defined at best. You could instead shuffle a known sequence of unique values and compare the result with the original to know how the elements were shuffled. For example, shuffle the sequence `0, 1, 2, ..., n`. — François Andrieux, Jun 08 '17 at 14:29
You could use a loop to keep shuffling until you get something that is equal to the original. Of course, this is not efficient for large strings... — Arnav Borborah, Jun 08 '17 at 14:33
Though `std::shuffle` is implementation-defined, it has an implementation that is equivalent to Fisher-Yates shuffle. And though `std::default_random_engine` is also implementation-defined, you can use it and the known seed to regenerate the shuffle order used in Fisher-Yates, then reverse the swaps manually. See https://stackoverflow.com/questions/3541378/reversible-shuffle-algorithm-using-a-key. — PaSTE, Jun 08 '17 at 14:34
why do you want to do this? Whatever you want to do with the unshuffled one, why dont you do it with the original string? — 463035818_is_not_an_ai, Jun 08 '17 at 14:37
if this is of purely academic interest, I have no idea how to do it, for anything else simply use `unshuffled = st` — 463035818_is_not_an_ai, Jun 08 '17 at 14:39
Possible duplicate of [Reversible shuffle algorithm using a key](https://stackoverflow.com/questions/3541378/reversible-shuffle-algorithm-using-a-key) — You, Jun 08 '17 at 14:48

score 4 · Accepted Answer · answered Jun 08 '17 at 14:39

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]

Unshuffle an array of int/char

1 Answers1

Linked