Reversing permutation of an array in Java efficiently

Question

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 permute the array a, using the order determined by array perm,

i.e. a=[a,b,c,d], perm=[2,3,4,1] ------> permutedA[b,c,d,a],

I figured out I can do that by iterating over the array with: permutedA[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 permutedA...

And now I want to do the reverse the permute 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]

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.

Answer 1

what's wrong with:

Collections.shuffle(Arrays.asList(theArray));

Answer 2

Think you mean

ShuffledA[i] = a[perm[i]-1]

At the time you shuffle you can build the inverse shuffle:

 inverseperm[perm[i]-1] = i + 1

Which builds

 inversePerm[4 1 2 3]

And you then apply your existing algorithm to [b c d a] yielding your original [a b c d]

Answer 3

Why permute it? Why not just access the items using the perm value.

for (int i=0; i<a.length; i++) {
  String val = a[perm[i]-1];
}

Answer 4

Quick and dirty example in Python:

def permute(a, perm):
    result = []
    for x in perm:
        result.append(a[x - 1])
    return result

def invPermute(a, perm):
    result = [None] * len(perm) # Build a result list of correct length
    for i, x in enumerate(a):
        result[perm[i] - 1] = x
    return result

Tested with:

>>> perm = [2,3,4,1]
>>> invPermute(permute("ABCD", perm), perm)
['A', 'B', 'C', 'D']