Минимальное количество операций обмена

Revision ru1, by altruist, 2017-07-02 16:01:52

Доброго времени суток, недавно я задумался над одной задачей, хочу поделиться с остальными: У вас есть два массива одинаковой длины n, вам нужно посчитать за какое минимальное количество операций обмена двух произвольных элементов первого массива из первого массива можно получить второй. (Элементы первого массива необязательно различны). В поисках эффективного решения Гугл меня ни к чему не привёл. Ясно как решать когда все элементы различны за O(n). Также предположительно есть решение за O(n) и для общего случая, но я не знаю как его проверить. Задача выглядит слишком баянисто. Знает кто как решать такое? Если знаете куда можно сдать, дайте ссылку.

Заранее спасибо!

Tags перестановки, permutations, minimum number of swaps

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English altruist 2017-07-03 16:05:02 518 Initial revision for English translation
ru1 Russian altruist 2017-07-02 16:01:52 719 Первая редакция (опубликовано)