Демистификация вопроса о структурах данных и алгоритмах - как выполнить перестановку массива на месте?
Снова наступили праздники, поэтому прежде всего я желаю всем счастливого Рождества и счастливого Нового года!
В один из выходных я получил старый вопрос, который был опубликован в Переполнении стека по алгоритму применения перестановки в постоянном пространстве памяти. Мне потребовалось несколько минут, чтобы найти решение этой проблемы.
Есть и другие варианты этого вопроса, поэтому я решу его на основе примера, приведенного в 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]
Если у вас есть какие-либо отзывы или что-то, чем вы хотите поделиться, не стесняйтесь оставлять комментарии 👇!