It seems to me there is more simple solution which uses O(1) space and O(n) time - just swap the permutation array (well, in real life I prefer not to use functions which are altering the input objects, but for the sake of space complexity)
Here code in Python
def apply_permutation(array, permutations):
for i in range(len(array)):
swap(array,i,permutations[i])
swap(permutations,i,permutations[i])
return array
def swap(array, i, j):
tmp = array[i]
array[i]=array[j]
array[j]=tmp
out = apply_permutation([‘a’,‘b’,‘c’,‘d’],[2,0,1,3])
print ("permutations are "+str(out))
self.assertEqual(out, [‘b’,‘c’,‘a’,‘d’])