У меня есть два массива A и B одинаковой длины.
A и B содержат одинаковые элементы, но в другом порядке.
Мне нужно сделать A совпадение B , только поменяв местами любые два элемента в A. Мне также нужно сделать это в минимально возможном количестве перестановок . Массив (ы) могут содержать повторяющиеся элементы.
Например, если
A = {3, 8, 5, 8}
B = {8, 8, 3, 5}
Минимально необходимый обмен составляет 2, а последовательность будет
swap(0, 2)
swap(0, 3)
Я знаю, как найти, сколько свопов нужно из таких источников, как здесь , или здесь , но я не могу найти информацию о , генерирующем последовательность свопов необходимо сделать A совпадение B. Я полагаю, что решение включает в себя ориентированные графы и циклы, но я не могу понять рабочий алгоритм, который меньше O (n ^ 2) времени.