将arrays1更改为arrays2所需的最小交换次数？

例如，input是

Array 1 = [2, 3, 4, 5] Array 2 = [3, 2, 5, 4] 

所需的最小交换次数是2 。

交换不需要与相邻的单元格交换，任何两个元素都可以交换。

Answer 1

正如@IVlad在对你的问题的评论中指出的那样， Yodaness问题要求你计算倒数的数量，而不是最小数量的掉期。

例如：

 L1 = [2,3,4,5] L2 = [2,5,4,3] 

最小交换次数是1 （ L2交换5和3来得到L1 ），但是反转次数是3 ：（5 4），（5 3）和（4 3）对的顺序是错误的。

根据定义计算反演次数的最简单方法如下：

如果i <j且p _i > p _j ，则一对元素（p _i ，p _j ）被称为置换p中的反转。

在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))) 

您可以使用分而治之策略（类似于合并sortingalgorithm的工作原理）计算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中的解决scheme：

 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 

Answer 2

正如塞巴斯蒂安的解决scheme所暗示的，您正在寻找的algorithm可以基于检查排列的周期 。

我们应该考虑数组＃2是数组＃1上的置换变换。 在你的例子中，排列可以表示为P = [2,1,4,3]。

每个置换可以表示为一组不相交的循环，表示项目的循环位置变化。 置换P例如有2个周期：（2,1）和（4,3）。 所以两次掉期就足够了。 在一般情况下，您应简单地从排列长度中减去循环次数，并且获得所需交换的最小数量。 这是由于观察到为了“固定”N个元素的周期，N-1个交换就足够了。

Answer 3

这个问题有一个干净，贪婪，微不足道的解决scheme：

1. find任何交换操作，使Array1中交换的元素更靠近Array2中的目标。 对Array1执行交换操作（如果存在）。
2. 重复第1步，直到不再有这样的交换操作存在。
3. find任何交换操作，使Array1中的一个交换元素更靠近Array2中的目标。 如果存在这样的操作，则在Array1上执行。
4. 回到step1，直到Array1 == Array2。

algorithm的正确性可以通过定义一个潜在的问题来certificate，就是array1中所有元素距array2中目的地的距离之和。

Answer 4

有可能是一些聪明的dynamic编程解决scheme，但我现在无法弄清楚。 你可以做一个朴素的BFS遍历使用这样的事情：

• 断言这是可能的（例如通过sorting和比较）
• 队列q = [（0，L1）]
• q不为空
  • 提取一些对（我，L）
  • 如果L == L2，则返回i
  • 对于每个0 <= i，j <= L1.length
    • 将（i + 1，L.swap（i，j））添加到q

更新 ：在Python中的实现（这是慢O（（N ³ ） ^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 

Answer 5

这可以很容易地转换成另一种types的问题，这可以更有效地解决。 所有需要的是将数组转换为排列，即将值更改为它们的ID。 所以你的数组：

 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）中的置换组合，然后find从那里到的交换次数，可以将置换从一个转换到另一个可以转换成类似问题（ 置换中的交换次数 ） 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) 

要计算这些步骤，可以devise一个简单的algorithm，例如：

 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; } 

这总是将一个物品换成一个应该在身份排列中的地方，因此在每一步它都会撤消并计算一次交换。 现在，假设它返回的交换次数确实是最小的，那么algorithm的运行时间就会受到限制，并保证完成（而不是陷入无限循环）。 它将以O(m)交换或O(m + n)循环迭代运行，其中m是交换count返回的count ）， n是序列（ 4 ）中项目的数量。 请注意， m < n始终为真。 因此，这应该优于O(n log n)解，因为这里的交换的上限是O(n - 1)或者是循环迭代的O(n + n - 1) ，实际上O(n) （在后一种情况下省略2的常数因子）。

该algorithm仅适用于有效置换，对于具有重复值的序列，它将无限循环，并且对具有[0, n)以外的值的序列进行超出边界的数组访问（和崩溃[0, n) 。 一个完整的testing用例可以在这里find（用Visual Studio 2008构build，algorithm本身应该相当便携）。 它生成长度为1到32的所有可能的排列，并检查用广度优先search（BFS）生成的解决scheme，似乎适用于长度为1到12的所有排列，然后它变得相当慢，但是我认为它将继续工作。

Answer 6

这似乎是一个编辑距离问题，除了只允许换位。

检查Damerau-Levenshtein距离伪代码。 我相信你可以调整它只计算换位。

Answer 7

algorithm：

1. 检查相同位置的列表元素是否相等。 如果是，则不需要交换。 如果不是，则交换元素匹配的list元素的位置
2. 遍历整个列表元素的过程。

码：

 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 

Answer 8

@JF Sebastian和@Eyal Schneider的回答很酷。 我从解决一个类似的问题得到启发： 计算sorting数组所需的最小交换次数 ，例如：对{2,1,3,0}进行sorting，您需要最less2次交换。

这是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; } // abbc // cabb // 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; }