Compiling multiple reverse permutations

Question

sorry if this isn't an appropriate question for here, it's just been melting my mind the last few hours and I'm sure I'm missing something obvious!

I've got a system set up which swaps the order of a series of entries in an array multiple times. For this I'm just using a Fisher-Yates swapping algorithm to create a corresponding array which where the corresponding index entry is to be moves to.

So what I want to be able to do is go back multiple steps. At the moment I'm trying to figure out the way of writing how I'd be able to get back from the second swap to the original order in a dynamically produced array using the two information from the swap arrays. I assume once I'm able to build one which goes back two steps in one go that I just keep applying the same approach to go back another step.

What would be the easiest approach of building an array of {'a','b','c','d'} using exclusively the information of swap[0], swap[1] and arr[1]? The code below is pretty much pseudocode, everything is working fine in the actual program asides from generating the reverse permutation thing.

    char theOriginal[4] = {'a', 'b', 'c', 'd'}; //the initial order
    int swap[x][4];
    char arr[x][4];

    /*below code would actually be generated using functions*/
    swap[0] = GetSwap(4); //eg. returns {2,3,0,1} generated using a Fisher-Yates swap

    arr[0] = Swappit(theOriginal, swap[0]); //returns {'c', 'd', 'a', 'b'} permuted array produced by function which rearranged theOriginal's values to correspond with swap[0]

    //all entries after the first one built in a loop
    for(z=1; z<x; z++){
        swap[z] = GetSwap(4); //e.g. return {1,3,2,0} another permutation built the same way

        arr[z] = Swappit(arr[z-1], swap[z]); //from swap[z]  applied to arr[0], we get {'d','b','a','c'}
    }

If that code is too confusingly worded to give an answer to easily, here's a more stripped down one you can use:

    char letters[4] = {'a', b', 'c', 'd'};

    int move1[4] = {2, 3, 0, 1};
    char reorder1[4] = {'c', 'd', 'a', 'b'};

    int move2[4] = {1, 3, 2, 0};
    char reorder2[4] = {'d', 'b', 'a', 'c'};

    /**something happens here so that using move1 and move2, 
    a new integer array can be built which will give a third 
    reordering which matches letters, ie the follow outputs**/
    int moveBack[4] = {2, 1, 3, 0};
    char reorderBack = {'a', 'b', 'c', 'd'};

luciole75w · Accepted Answer · 2014-04-28 13:56:28Z

You simply have to compute the inverse permutation for each step and apply them in reverse order.

If you have a forward permutation P defined as

moveP[0] = n0
moveP[1] = n1
moveP[2] = n2
moveP[3] = n3

then you compute the corresponding inverse permutation P^-1 such as

movePinv[n0] = 0
movePinv[n1] = 1
movePinv[n2] = 2
movePinv[n3] = 3

That way you have P^-1(Y) = X if P(X) = Y.

In your example, if you start from array A0 and apply 2 permutations P and Q, giving the steps A1 = P(A0) and A2 = Q(A1) = Q(P(A0)), then to get back the initial array A0, you have to apply the inverse permutations in reverse order to the final array. That is A1 = Q^-1(A2) then A0 = P^-1(A1) = P^-1(Q^-1(A2)).

Note that for an improved memory usage you can definitely do this incrementally, accumulating all the inverse permutations in a single one (assuming you are only interested in retrieving the initial order but not the intermediate steps of course).

Edit : following your code, here is what the backward step could look like to. It's clearly not great if you plan to do it several times (since the inverse permutations would be computed and applied to the source array each time), but for a one-shot, it's the simplest way.

int backFrom = x - 1, backTo = 0; // for example
char state[4] = arr[backFrom];
int swapInvAux[4];

for (z = backFrom; z >= backTo; --z)
{
    swapInvAux = InversePermutation(swap[z]);

    state = Swappit(state, swapInvAux);
}

For better performance, parallel to the swap array you should store a chain of accumulated inverse permutations obtained by applying your Swappit function to the swap array itself. Doing so you would be able to reverse the final state to any intermediate state in a single step.

Collectives™ on Stack Overflow

Compiling multiple reverse permutations

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related