Например, ввод
Array 1 = [2, 3, 4, 5]
Array 2 = [3, 2, 5, 4]
Минимальное количество необходимых свопов - 2.
Смены не обязательно должны быть со смежными ячейками, любые два элемента могут быть заменены.
Минимальное количество свопов, необходимых для изменения массива 1 на массив 2?
Ответ 1
Как @IVlad отметил в комментарии к вашему вопросу проблема Yodaness просит вас посчитать количество инверсий, а не минимальное количество свопов.
Например:
L1 = [2,3,4,5]
L2 = [2,5,4,3]
Минимальное количество свопов - это один (обмен 5 и 3 в L2, чтобы получить L1), но число инверсий равно трем: (5 4), (5 3) и (4 3) пары в неправильном порядке.
Самый простой способ подсчета числа инверсий следует из определения:
Пара элементов (p i, p j) называется инверсией в перестановке p, если я < j и p i > р <югу > Jсуб > .
В Python:
def count_inversions_brute_force(permutation):
"""Count number of inversions in the permutation in O(N**2)."""
return sum(pi > permutation[j]
for i, pi in enumerate(permutation)
for j in xrange(i+1, len(permutation)))
Вы можете рассчитывать инверсию в O(N*log(N)), используя стратегию разделения и завоевания (подобно тому, как работает алгоритм сортировки слиянием). Здесь псевдокод из Counting Inversions переведен на код Python:
def merge_and_count(a, b):
assert a == sorted(a) and b == sorted(b)
c = []
count = 0
i, j = 0, 0
while i < len(a) and j < len(b):
c.append(min(b[j], a[i]))
if b[j] < a[i]:
count += len(a) - i # number of elements remaining in `a`
j+=1
else:
i+=1
# now we reached the end of one the lists
c += a[i:] + b[j:] # append the remainder of the list to C
return count, c
def sort_and_count(L):
if len(L) == 1: return 0, L
n = len(L) // 2
a, b = L[:n], L[n:]
ra, a = sort_and_count(a)
rb, b = sort_and_count(b)
r, L = merge_and_count(a, b)
return ra+rb+r, L
Пример:
>>> sort_and_count([5, 4, 2, 3])
(5, [2, 3, 4, 5])
Здесь решение в Python для примера из проблема:
yoda_words = "in the force strong you are".split()
normal_words = "you are strong in the force".split()
perm = get_permutation(normal_words, yoda_words)
print "number of inversions:", sort_and_count(perm)[0]
print "number of swaps:", number_of_swaps(perm)
Вывод:
number of inversions: 11
number of swaps: 5
Определения get_permutation() и number_of_swaps():
def get_permutation(L1, L2):
"""Find permutation that converts L1 into L2.
See http://en.wikipedia.org/wiki/Cycle_representation#Notation
"""
if sorted(L1) != sorted(L2):
raise ValueError("L2 must be permutation of L1 (%s, %s)" % (L1,L2))
permutation = map(dict((v, i) for i, v in enumerate(L1)).get, L2)
assert [L1[p] for p in permutation] == L2
return permutation
def number_of_swaps(permutation):
"""Find number of swaps required to convert the permutation into
identity one.
"""
# decompose the permutation into disjoint cycles
nswaps = 0
seen = set()
for i in xrange(len(permutation)):
if i not in seen:
j = i # begin new cycle that starts with `i`
while permutation[j] != i: # (i σ(i) σ(σ(i)) ...)
j = permutation[j]
seen.add(j)
nswaps += 1
return nswaps
Ответ 2
Как подразумевается решением Себастьяна, алгоритм, который вы ищете, может быть основан на проверке циклов перестановки .
Мы должны рассмотреть массив # 2 как преобразование перестановки в массиве # 1. В вашем примере перестановка может быть представлена как P = [2,1,4,3].
Каждая перестановка может быть выражена как набор непересекающихся циклов, представляющих циклические изменения позиций элементов. Перестановка P, например, имеет 2 цикла: (2,1) и (4,3). Поэтому достаточно двух свопов. В общем случае вы должны просто вычесть количество циклов из длины перестановки и получить минимальное количество необходимых свопов. Это следует из наблюдения, что для "исправления" цикла из N элементов достаточно смены N-1.
Ответ 3
Эта проблема имеет чистое, жадное, тривиальное решение:
- Найти любую операцию свопинга, которая получает обе, заменяемые элементы в массиве Array1 ближе к месту назначения в Array2. Выполните операцию свопинга на Array1, если таковая существует.
- Повторите шаг1 до тех пор, пока не будут выполнены такие операции свопинга.
- Найти любую операцию свопинга, которая получает один измененный элемент в массиве Array1 ближе к его месту назначения в Array2. Если такая операция существует, выполните ее на Array1.
- Вернитесь к шагу 1, пока Array1 == Array2.
Правильность алгоритма может быть доказана путем определения потенциала задачи как суммы расстояний всех элементов в массиве 1 от их адресата в массиве2.
Ответ 4
Возможно, существует некоторое интеллектуальное решение динамического программирования, но я не могу понять это сейчас. Вы можете совершить наивный обход BFS, используя что-то вроде этого:
- утверждают, что это возможно (например, путем сортировки и сравнения)
- Очередь q = [(0, L1)]
- Пока q не пуст
- извлеките некоторую пару (i, L)
- если L == L2, верните i
- для каждого 0 <= i, j <= L1.length
- добавить (i + 1, L.swap(i, j)) в q
UPDATE: реализация в Python (медленная O ((N 3) n))
def bfs(L1, L2):
assert sorted(L1) == sorted(L2)
q = deque([ (0,L1) ])
while q:
n, L = q.popleft()
if L == L2: return n
for i, j in combinations(range(len(L1)), 2): # all N*(N-1)/2 pairs
q.append((n+1, swap(L, i, j)))
from collections import deque
from itertools import combinations
def swap(L, i, j):
a = list(L) # make copy
a[i], a[j] = a[j], a[i] # swap
return a
Ответ 5
Это может быть легко преобразовано в проблему другого типа, которая может быть решена более эффективно. Все, что нужно, это преобразовать массивы в перестановки, т.е. Изменить значения на их идентификаторы. Итак, ваши массивы:
L1 = [2,3,4,5]
L2 = [2,5,4,3]
станет
P1 = [0,1,2,3]
P2 = [0,3,2,1]
с присваиванием 2->0, 3->1, 4->2, 5->3. Это можно сделать, только если нет повторяющихся элементов. Если есть, то это становится сложнее решить.
Преобразование перестановки из одного в другое может быть преобразовано в аналогичную проблему (Число свопов в перестановке), инвертируя целевую перестановку в O (n), составив перестановки в O (n), а затем нахождение числа свопов оттуда до подстановки подстановки в O (m). Данный:
int P1[] = {0, 1, 2, 3}; // 2345
int P2[] = {0, 3, 2, 1}; // 2543
// we can follow a simple algebraic modification
// (see http://en.wikipedia.org/wiki/Permutation#Product_and_inverse):
// P1 * P = P2 | premultiply P1^-1 *
// P1^-1 * P1 * P = P1^-1 * P2
// I * P = P1^-1 * P2
// P = P1^-1 * P2
// where P is a permutation that makes P1 into P2.
// also, the number of steps from P to identity equals
// the number of steps from P1 to P2.
int P1_inv[4];
for(int i = 0; i < 4; ++ i)
P1_inv[P1[i]] = i;
// invert the first permutation in O(n)
int P[4];
for(int i = 0; i < 4; ++ i)
P[i] = P2[P1_inv[i]];
// chain the permutations in O(n)
int num_steps = NumSteps(P, 4); // will return 2
// now we just need to count the steps in O(num_steps)
Чтобы подсчитать шаги, можно разработать простой алгоритм, например:
int NumSteps(int *P, int n)
{
int count = 0;
for(int i = 0; i < n; ++ i) {
for(; P[i] != i; ++ count) // could be permuted multiple times
swap(P[P[i]], P[i]); // look where the number at hand should be
}
// count number of permutations
return count;
}
Это всегда заменяет элемент для места, где он должен находиться в перестановке идентичности, поэтому на каждом шаге он отменяет и подсчитывает один своп. Теперь, при условии, что количество возвращаемых им свопов действительно минимально, время выполнения алгоритма ограничено им и гарантируется завершение (вместо того, чтобы застревать в бесконечном цикле). Он будет выполняться в циклах O(m) или O(m + n), где m - количество свопов (возвращается count), а n - количество элементов в последовательности (4). Обратите внимание, что m < n всегда истинно. Следовательно, это должно быть выше решений O(n log n), так как верхняя граница O(n - 1) свопов или O(n + n - 1) итераций цикла здесь, которая практически равна O(n) (постоянный коэффициент 2 опущен в последнем случае).
Алгоритм будет работать только для действительных перестановок, он будет бесконечно циклически перемещаться для последовательностей с повторяющимися значениями и будет делать доступ к массиву вне пределов (и сбоев) для последовательностей со значениями, отличными от [0, n). Полный тестовый пример можно найти здесь (строит с помощью Visual Studio 2008, сам алгоритм должен быть довольно портативным). Он генерирует все возможные перестановки с длиной от 1 до 32 и проверяет на решения, сгенерированные с помощью первого поиска ширины (BFS), похоже, работает для всех перестановок длиной от 1 до 12, тогда он становится довольно медленным, но я предполагаю, что он просто продолжит работу.
Ответ 6
Это похоже на проблему изменить расстояние, за исключением того, что разрешены только транспозиции.
Отъезд Дамерау-Левенштейн расстояние псевдокод. Я считаю, что вы можете настроить его, чтобы считать только транспозиции.
Ответ 7
Алгоритм:
- Проверьте, равны ли элементы списка в одном и том же положении. Если да, обмен не требуется. Если нет, замените позицию элемента списка везде, где элемент соответствует
- Итерировать процесс для всех элементов списка.
Код:
def nswaps(l1, l2):
cnt = 0
for i in range(len(l1)):
if l1[i] != l2[i]:
ind = l2.index(l1[i])
l2[i], l2[ind] = l2[ind], l2[i]
cnt += 1
pass
return cnt
Ответ 8
Поскольку мы уже знаем, что arr2 имеет правильные индексы каждого элемента, присутствующего в arr1. Следовательно, мы можем просто сравнить элементы arr1 с arr2 и поменять их местами с правильными индексами, если они имеют неправильный индекс.
def minimum_swaps(arr1, arr2):
swaps = 0
for i in range(len(arr1)):
if arr1[i] != arr2[i]:
swaps += 1
element = arr1[i]
index = arr1.index(arr2[i]) # find index of correct element
arr1[index] = element # swap
arr1[i] = arr2[i]
return swaps
Ответ 9
@J.F. Ответ Себастьяна и Эяля Шнайдера довольно крутой.
Я был вдохновлен на решение аналогичной проблемы: Рассчитать минимальные свопы, необходимые для сортировки массива, например: для сортировки {2,1,3,0} вам потребуется минимум 2 свопа.
Вот код Java:
// 0 1 2 3
// 3 2 1 0 (0,3) (1,2)
public static int sortWithSwap(int [] a) {
Integer[] A = new Integer[a.length];
for(int i=0; i<a.length; i++) A[i] = a[i];
Integer[] B = Arrays.copyOf(mapping(A), A.length, Integer[].class);
int cycles = 0;
HashSet<Integer> set = new HashSet<>();
boolean newCycle = true;
for(int i=0; i<B.length; ) {
if(!set.contains(B[i])) {
if(newCycle) {
newCycle = false;
cycles++;
}
set.add(B[i]);
i = B[i];
}
else if(set.contains(B[i])) { // duplicate in existing cycles
newCycle = true;
i++;
}
}
// suppose sequence has n cycles, each cycle needs swap len(cycle)-1 times
// and sum of length of all cycles is length of sequence, so
// swap = sequence length - cycles
return a.length - cycles;
}
// a b b c
// c a b b
// 3 0 1 1
private static Object[] mapping(Object[] A) {
Object[] B = new Object[A.length];
Object[] ret = new Object[A.length];
System.arraycopy(A, 0, B, 0, A.length);
Arrays.sort(A);
HashMap<Object, Integer> map = new HashMap<>();
for(int i=0; i<A.length; i++) {
map.put(A[i], i);
}
for(int i=0; i<B.length; i++) {
ret[i] = map.get(B[i]);
}
return ret;
}