Демистификация вопроса о структурах данных и алгоритмах - как выполнить перестановку массива на месте?

Снова наступили праздники, поэтому прежде всего я желаю всем счастливого Рождества и счастливого Нового года!

В один из выходных я получил старый вопрос, который был опубликован в Переполнении стека по алгоритму применения перестановки в постоянном пространстве памяти. Мне потребовалось несколько минут, чтобы найти решение этой проблемы.

Есть и другие варианты этого вопроса, поэтому я решу его на основе примера, приведенного в Stack Overflow.

Обратите внимание, что все, что написано в этой статье, имеет нулевой индекс, так как я буду использовать Python.

Дано 2 массива: A и P, где A - это массив, содержащий элементы, которые должны быть «переставлены» или, скорее, переупорядочены на основе массива P, который содержит индексы нового порядка каждого элемента в массиве A, алгоритм должен переупорядочить массив A с постоянной сложностью памяти, O (1).

# Array of elements to be reordered
A = [ 'a', 'b', 'c', 'd', 'e' ]
# Array of the indices of the new order
P = [ 4, 3, 2, 0, 1 ]

В приведенном выше примере должно получиться следующее решение:

A = [ 'e', 'd', 'c', 'a', 'b' ]

На первый взгляд этот вопрос может показаться непростым. Но если бы вы использовали этот пример и попытались найти способ решить эту проблему на месте, на самом деле решение было бы довольно простым. Давайте еще раз воспользуемся тем же примером и попробуем решить его!

Нам нужно будет просмотреть все элементы A и P, чтобы выполнить перестановку. Начнем с первого элемента:

Первый элемент P сообщает нам, что первый элемент должен быть 4-м элементом индекса A, то есть символом e. Мы делаем замену, чтобы вставить e на место.

Поскольку e - это место, перейдем к следующему элементу.

Теперь нам нужно заменить символ b на d и перейти к следующему индексу.

Поскольку символ c уже находится в правильном положении, мы можем перейти к следующему.

А теперь самое сложное. Символ b должен быть заменен 0-м элементом, который изначально был символом a, но символ a теперь находится в новой позиции 4.

Мы застряли? Вообще-то, нет!

Если вы присмотритесь, вы заметите, что 0-й элемент массива P указывает на исходный 0-й элемент A .

Подумайте об этом рационально, если текущий элемент в P ссылается на прошлое, например, с индексом 3, P [3] фактически указывает на индекс 0, который уже был обработан ранее, поскольку текущий индекс равен 3, а индекс 0 находится перед 3, это означает, что вполне вероятно, что он был заменен элементом в 0.

При P [3] = 0 и принятии этого в качестве нового индекса P [0] = 4 фактически указывает на новое местоположение исходного 0-го элемента в A [4]! Мы можем использовать P, чтобы отследить, что мы поменяли местами, и соответственно поменять местами нужные.

Поменяв местами символы a и b, мы перейдем к последнему элементу, на который нужно посмотреть.

Есть два способа взглянуть на этот последний элемент.

Первый способ заключается в том, что, поскольку мы уже достигли последнего элемента, все элементы до него уже находятся в правильном положении. Следовательно, этот последний элемент находится в правильном положении, и мы можем просто завершить перестановку.

Второй способ заключается в том, что последний элемент P на самом деле равен 1, а 1 указывает на прошлое, поскольку текущий индекс равен 4. Нам нужно будет сделать замену!

Мы отслеживаем до P [1], который равен 3, а 3 меньше текущего индекса 4.

Мы продолжим трассировку от P [3], который указывает на 0, а 0 меньше текущего индекса 4.

Мы снова проследим за точкой P [4], которая указывает на 4, а 4 равно текущему индексу, мы остановимся.

После этого мы получили переупорядоченный массив A!

Ничто не говорит громче рабочего кода, так что вот он:

def permutate(A, P):
    # Iterate through every element in the given arrays
    for i in range(len(A)):
        # We look at P to see what is the new index
        index_to_swap = P[i]
        # Check index if it has already been swapped before
        while index_to_swap < i:
            index_to_swap = P[index_to_swap]
        # Swap the position of elements
        A[i], A[index_to_swap] = A[index_to_swap], A[i]

Если у вас есть какие-либо отзывы или что-то, чем вы хотите поделиться, не стесняйтесь оставлять комментарии 👇!