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] + i) % 10;
s = data[i];
data[i] = 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 it work with an arbitrarily sized array, but it's not required.
Edit: If it would be easier to just dump this and go with a different reversible data-driven shuffling algorithm I'm all ears.
Could you not just go with a algorithm that is like "shuffle to the right 3, then shuffle to the left 3 on the next element...etc..." ? Because if you shuffle it without a sequential set of instructions there will be no way of determining the original input
PS: 4k posts
Ideally I'd like it to shuffle differently depending on the contents of the array. I just figured that, knowing the algorithm as well as the fact that all of the data is provided, it would be possible to reverse the shuffling.
And I should probably cut it down to 8 elements, since the first and last are checksum and parity, respectively, and so it would be easier to reject incorrect results sooner since neither relies on the position of the data.
(2011-07-13, 10:27 PM)Firestryke31 Wrote: [ -> ]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] + i) % 10;
s = data[i];
data[i] = 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.
you can use
rand() (something like "
j = i + (rand()%(10-i))" ) function to randomly choose a position to shuffle with the current position and you can save the positions to another array or something so that you can un-shuffle it later.
(2011-07-13, 10:27 PM)Firestryke31 Wrote: [ -> ]Bonus cookies if you can make it work with an arbitrarily sized array, but it's not required.
In that case I think you might wanna use linked list instead of an array. With linked list you can create any node where ever you want in the program..
(2011-07-14, 02:30 AM)techu Wrote: [ -> ]you can use rand() (something like "j = i + (rand()%(10-i))" ) function to randomly choose a position to shuffle with the current position and you can save the positions to another array or something so that you can un-shuffle it later.
The problem is that the data I'm shuffling is the only thing transmitted, and I can't rely on the rand() implementation to be the same on all computers.
(2011-07-14, 02:30 AM)techu Wrote: [ -> ]In that case I think you might wanna use linked list instead of an array. With linked list you can create any node where ever you want in the program..
The arbitrary size thing was more for reusability, i.e. right now it's 10 elements, but I might want to do it to a 15 element array in a different program or an 8 element array in yet another. The size is static, but the algorithm should be able to handle any size I give it. My shuffle code is easy to expand, just replace '10' with a parameter 'n.' I would like the decode algorithm to be the same way.
The problem is, the algorith must be independent of the data. Otherwise you'll never get back to the original. Your best bet would be to have a function that moves the first element "right 3" the second element "left5" and a third element "right 3", then repeat the sequence a known number if times.
Then to reverse it you simply do it backwards, flipping the direction ("right 3" becomes "left 3") and repeating this the same number of times.
Why do you need to shuffle the data anyway?
Firestryke31 Wrote:This is mostly to help keep 2 sequential things from generating sequential output
Yeah, someone over at gamedev.net explained why. I was thinking of not shuffling the first or last elements and shuffling the innards based off of those. Since the first and last remain in place, it'd be easy to get the original shuffle steps, and it's still data-dependent since the elements are a checksum and parity. It also moves a key validation step to before unshuffling so I can throw out invalid data earlier rather than later.
Im fairly sure doing a data dependent shuffle is non reversible, unless you keep some kind of record as to how it was shuffled. Essentially you are performing a message digest, hence why MD5 is non-reversible.
If you have the array:
"a,c,c,g,t,p,w,c,r,s,h"
and you shuffle them based on their position in the alphabet you would get:
"a,c,c,c,g,h,p,r,s,t,w"
From there, there is no way of determining the original input
Well, I kind of got around that when I rewrote the algorithm. It's still dependent on the data since the values I use to seed the system are the checksum and parity bytes, but it's reversible because those values don't move so I can just replay the shuffle in reverse using them as the seed.
I have the code I used
here if anybody cares.