Реверсивная перестановка массива в Java эффективно

Question

Хорошо, вот моя проблема:

Я реализую алгоритм на Java, и его часть будет следующей: Вопрос в том, как сделать то, что я сейчас объясню, эффективным способом.

Дано: массив длины n целочисленный массив perm, который является перестановкой [1..n]

теперь я хочу переставить массив a, используя порядок, определенный массивом perm,

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

Я понял, что могу сделать это путем перебора массива с помощью: permutedA [i] = a [perm [i] -1], (-1, потому что индексы перестановки в perm начинаются с 1, а не с 0)

Теперь я хочу сделать некоторые операции с permutedA ...

А теперь я хочу сделать операцию перестановки в обратном порядке. Это где я не уверен, как это сделать. Обратите внимание, что элемент a может содержать элемент более одного раза, то есть a = [a, a, a, a]

Теперь я подумал, что использование Hashmap вместо массива perm поможет. Но я не уверен, что это лучший способ сделать это.

Answer 1

думаю, что вы имеете в виду

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

В то время, когда вы тасуете, вы можете создать обратный тасовку:

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

Который строит

 inversePerm[4 1 2 3]

И затем вы применяете свой существующий алгоритм к [b c d a], получая свой оригинал [a b c d]

Answer 2

Зачем переставлять? Почему бы просто не получить доступ к элементам, используя значение perm.

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

Answer 3

Быстрый и грязный пример в 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

Проверено с:

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

Answer 4

что не так с:

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