Jump to content
  • Advertisement
Sign in to follow this  
Firestryke31

Algorithm Help

This topic is 2563 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Alright, I've got a bit of C++ code that I've written that takes the numbers in an array of 10 elements and shuffles them:

char s = 0;
int j = 0;
for(int i = 0; i < 10; ++i)
{
j = (data + i) % 10;
s = data;
data = data[j];
data[j] = s;
}


My problem is, I need to be able to undo this shuffling at a later point, not necessarily in the same run of the program. Unfortunately, I cannot for the life of me figure out how to do so algorithmically.

Some sample output of the above:

STRT: 3E 46 6F 78 78 67 30 01 01 40
SHF0: 6F 46 3E 78 78 67 30 01 01 40
SHF1: 6F 46 3E 78 78 67 30 01 01 40
SHF2: 6F 46 78 78 3E 67 30 01 01 40
SHF3: 6F 46 78 78 3E 67 30 01 01 40
SHF4: 6F 46 78 78 30 67 3E 01 01 40
SHF5: 6F 46 78 78 30 01 3E 01 67 40
SHF6: 6F 46 78 78 30 01 67 01 3E 40
SHF7: 6F 46 78 78 30 01 67 3E 01 40
SHF8: 6F 46 78 78 30 01 67 3E 40 01
SHF9: 01 46 78 78 30 01 67 3E 40 6F


It's not really shuffling it, so much as moving things around in a data-dependent way. This is mostly to help keep 2 sequential things from generating sequential output, especially after a few more steps I take to help muddle things up some more. So far everything's reversible except for this "shuffling."

Bonus cookies if you can make the unshuffling work with an arbitrarily sized array, but it's not required. I might change the whole thing to forgo shuffling the first and last elements since they're a checksum and parity, respectively, and I'd like to make it easier to reject incorrect input earlier rather than later. If it would be easier to just dump this and go with a different reversible data-driven shuffling algorithm I'm all ears.

Also, if this algorithm has a name I would be interested in knowing it.

Share this post


Link to post
Share on other sites
Advertisement
Your example output does not make sense. Why are SHF0 and SHF1 equal? (And what does SHF mean...)

What you want is impossible, your operation is not reversible. There's no way for the output to be { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } (e: for that matter, any sequence where x % 10 != (i + 1) % 10 for all i), and there are finitely many possible permutations of these numbers -- that's how we know your output is not reversible (it's by the pigeonhole principle).

Share this post


Link to post
Share on other sites

Your example output does not make sense.


How so? It's the starting array, plus the array for each iteration of i.


What you want is impossible, your operation is not reversible. There's no way for the output to be { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, and there are finitely many possible permutations of these numbers -- that's how we know your output is not reversible (it's by the pigeonhole principle).


I just figured that since the algorithm uses the given data (and only the given data) to perform the shuffle, it would be possible to unshuffle it given the output.

Share this post


Link to post
Share on other sites
Unless I'm royally screwing up my math here, this is irreversible.

The modulus division discards information which is necessary for reconstructing the flow of elements. Consider a simple case:

Input: {1, 2, 3}

Pass 1: (data[0] + 0) % 3 = (1 + 0) % 3 = 1
Swap 0, 1
Result: {2, 1, 3}

Pass 2: (data[1] + 1) % 3 = (1 + 1) % 3 = 2
Swap 1, 2
Result: {2, 3, 1}

Pass 3: (data[2] + 2) % 3 = (1 + 2) % 3 = 0
Swap 2, 0
Result: {1, 3, 2}

Now, we try to reverse, starting with index 2. We know that the equation will look like this: (data[x] + 2) % 3 = y. With the benefit of hindsight, we know that x is 2 and therefore y is 0; but without that knowledge, we don't know x or y. Even if we knew the value of data[x], we couldn't simply substitute that and solve for y, because the modulus division has infinitely many solutions. If we know the value of y alone, we still can't solve for data[x] because of the same problem. And even if we know what data[x] is, that doesn't help us find x because there may be many duplicate values in the list. Therefore, we cannot reverse this process without storing the indexes which were reversed by each step.

At that point, you have to store the entire chain of swaps to reverse the order; this is a seriously not good situation. It gains us nothing over simply randomly shuffling the original list and recording the list of swaps that way.

A better solution would be to compute a position-independent hash of the input values, use that as a seed into a pseudorandom number generator, and then generate a pseudorandom sequence of swaps. If you use the first value out of the PRNG as the number of swaps to make, you can do this:

  • Compute hash, seed PRNG
  • Randomly choose how many swaps n to make
  • Generate n*2 random numbers; use them to swap values
    Reversing is simple:

    • Compute hash, seed PRNG
    • Generate swap count n
    • Generate n*2 random numbers and store them
    • Reverse the list of random numbers
    • Perform the swaps given by the reversed list

Share this post


Link to post
Share on other sites

A better solution would be to compute a position-independent hash of the input values, use that as a seed into a pseudorandom number generator, and then generate a pseudorandom sequence of swaps. If you use the first value out of the PRNG as the number of swaps to make, you can do this:


You might as well use a fixed seed, and use it to do a fair random shuffle.

Share this post


Link to post
Share on other sites
Conside this array

15 17 6 2 9 18 12 2 5 8

At i=0
(a[0] + 0) % 10 = 5
swapping a[0] and a[5]

After first iteration the array would become
18 17 6 8 9 15 12 2 5 8

Even after the first iteration, you can't revert it back.

To get the value of 0th position, you have to do the following check.
for all i except 0,
(a+i) % 10 should be 0

In this case its the 5th position, (a[5] + 5) % 10 = 0 (swapped from 0th position)
and the 7th position, (a[7]+7) % 10 = 0 (swapped from 0th position)

So how would you know from which position it (18) was swapped (either 5th or 7th)?

It is irreversible even after the first iteration.
How can you be sure after 10 iterations where more than one swaps can be there for a single position?

Share this post


Link to post
Share on other sites
How about something like this:

#include <iostream>
#include <vector>
#include <cstdlib>

void main() {
// intialise swaps
std::srand(0);
const int n(10);
std::vector<int> swaps(n);
for (int i = 0; i < n; ++i) {
swaps = std::rand() % n;
}

// initialise data
std::vector<int> data(n);
for (int i = 0; i < n; ++i) {
data = i;
}
std::ostream_iterator<int> out(std::cout, ", ");
std::copy(data.begin(), data.end(), out);
std::cout << '\n';

// shuffle
for (int i = (n - 1); i >= 0; --i) {
std::swap(data, data[swaps]);
}
std::copy(data.begin(), data.end(), out);
std::cout << '\n';

// deshuffle
for (int i = 0; i < n; ++i) {
std::swap(data[swaps], data);
}
std::copy(data.begin(), data.end(), out);
std::cout << '\n';
}


You just need to make sure that the random number generator is seeded to the same number.

Share this post


Link to post
Share on other sites

What are your requirements, what is the bigger problem you're trying to solve?


Mostly to help keep sequential input from becoming sequential output while still maintaining the original data.

I'm probably going to change the system to not shuffle the first and last positions, and to shuffle the innards based solely off of some combination of the two. That should be reversable, right?

Share this post


Link to post
Share on other sites
Why does the random shuffle have to have anything to do with the data contents? Can't you just generate a seed and store that seed along with the data stream, and use that seed to reconstruct the shuffling pattern, as has been suggested several times now in this thread?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!