Reversing permutation of an array in Java efficiently
- by HansDampf
Okay, here is my problem:
Im implementing an algorithm in Java and part of it will be following:
The Question is to how to do what I will explain now in an efficient way.
given:
array a of length n
integer array perm, which is a permutation of [1..n]
now I want to shuffle the array a, using the order determined by array perm,
i.e.
a=[a,b,c,d], perm=[2,3,4,1] ------ shuffledA[b,c,d,a],
I figured out I can do that by iterating over the array with: shuffledA[i]=a[perm[i-1]], (-1 because the permutation indexes in perm start with 1 not 0)
Now I want to do some operations on shuffledA...
And now I want to do the reverse the shuffle operation.
This is where I am not sure how to do it.
Note that a can hold an item more than once, i.e. a=[a,a,a,a]
If that was not the case, I could iterate perm, and find the corresponding indexes to the values.
Now I thought that using a Hashmap instead of the the perm array will help. But I am not sure if this is the best way to do.
