将数组1转换为数组2所需的最小交换次数是多少？

Question

例如，输入为

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

最少需要2次交换。

交换的元素不一定要相邻，任意两个元素都可以交换。

https://www.spoj.com/problems/YODANESS/

- Dogbert

---

我正在尝试 https://www.spoj.pl/problems/YODANESS/。 - Dogbert

这个问题似乎要求你计算逆序对，而不是你在这里询问的内容。 - IVlad

询问SPOJ问题的解决方案是正确的方法吗？难道你不应该自己尝试解决吗？为什么不寻求提示而不是答案呢？ - MAK

我认为这在很大程度上取决于列表是否允许重复。如果不允许，那么这个问题相当简单，但如果允许，则相当棘手。 - Martin Ender

相关：计算将一个排列转换为另一个排列所需的相邻交换次数 - jfs

高度相关：计算排序序列所需的最小交换次数 - Bernhard Barker

Answer 1

正如 @IVlad 在你的问题的评论中指出的那样，Yodaness 问题 要求你计算逆序对数而不是最少交换次数。

例如：

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

最少的交换次数是 一次 (将 L2 中的 5 和 3 交换以得到 L1)，但逆序对的数量为 三个：(5 4), (5 3) 和 (4 3) 这几对在错误的顺序中。

计算逆序对的最简单方法遵循定义：

在排列 p 中，如果 i < j 且 p_i > p_j，则元素对 (p_i,p_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))的时间复杂度内计算逆序对。以下是来自计数逆序对的伪代码，已翻译为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

- jfs

---

如果输入文本中有重复的内容，它们是否需要特殊索引？请问。 - Bob Templ

问题仅针对不同的单词进行明确定义。只要满足前/后置条件，您可以随意定义get_permutation，例如使用((v，L1.count(v)), i)（或其更有效的等效形式）而不是(v，i)。 - jfs

那似乎会导致相同的结果。例如，在两个输入“'kamal'”和“'amalk'”上使用任一方法都会生成一个看起来像“[3,2,3,4,0]”的排列；理想情况下，它应该是“[1,2,3,4,0]”。我想我还应该注意，即使手动传递排列“[1,2,3,4,0]”，当实际上最小值为3时，我也会得到4次交换；kamal -> akmal -> almak -> amalk。 - Bob Templ

我是指“迄今为止v出现的次数”而不是L1.count（即 list(<the dict>).count(v)）否则会有重复值（将assert sorted(set(permutation)) == range(len(permutation)) 添加到后置条件中）。虽然正如您的示例所示，这还不够。我认为重复项的扩展值得单独提问。 - jfs

@BobTempl: almak -> amalk 移动了 3 个字母，而不是 2，即如果 get_permutation() 被适应用于带有重复的序列，则 number_of_swaps() 在这种情况下也可以工作。我已经为带有重复的情况调整了 get_permutation() 函数（它基于 与相关问题的 @IVlad 的答案中的算法）。 - jfs

Answer 2

正如Sebastian的解决方案所暗示的那样，你要寻找的算法可以基于检查置换的循环。

我们应该将数组#2视为对数组#1的置换变换。在你的例子中，置换可以表示为P=[2,1,4,3]。

每个置换都可以表示为一组不相交的循环，代表物品的循环位置变化。例如，置换P有两个循环：(2,1)和(4,3)。因此，只需要进行两次交换。在一般情况下，你只需从置换长度中减去循环数，就可以得到所需最小交换次数。这是因为观察到为了“修复”包含N个元素的循环，只需要进行N-1次交换。

- Eyal Schneider

Answer 3

这个问题有一个简单、贪心、琐碎的解决方案：

1. 找到任何一种交换操作，使得Array1中被交换的两个元素都更接近它们在Array2中的目标位置。如果存在这样的交换操作，则在Array1上执行该操作。
2. 重复步骤1，直到不存在更多的这样的交换操作为止。
3. 找到任何一种交换操作，使得Array1中被交换的一个元素更接近它在Array2中的目标位置。如果存在这样的操作，则在Array1上执行它。
4. 回到步骤1，直到Array1 == Array2。

通过将问题的潜力定义为array1中所有元素与array2中目标位置的距离之和，可以证明算法的正确性。

- Yuval Cohen

Answer 4

算法：

1. 检查列表中相同位置的元素是否相等。如果是，则不需要交换。如果不是，则在元素匹配的位置交换列表元素的位置。
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

- Ishwor Bhatta

---

请解释你的代码和算法。与其他回答相比，这个代码转储非常低质量。你有带来任何新东西吗？ - Nic3500

Answer 5

这个问题可以很容易地转换成另一种类型的问题，从而更有效地解决。所需的只是将数组转换为排列，即将值更改为它们的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)组合排列，然后在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的所有排列，然后变得相当缓慢，但我认为它将继续工作。

- the swine

---

没有必要将这个问题转化为另一个需要与原问题同样的努力的问题，转化为不同的问题需要解决一个更简单的问题，但你的答案并非如此。在这里找到循环，从而确定交换次数是最好的方法。 - MithunS

@MithunS 注意当前被接受的答案是如何先形成一个排列，然后执行类似的算法。该答案附带代码、测试和证明，还展示了该问题与其他问题的关系。感谢你的点踩。 - the swine

下降的原因是您对索引的转换是不必要的。此外，您不需要在数组上运行3个循环来完成此操作。 您能解释一下您的转换如何使解决方案更有效吗？ 您知道要找出所需交换的最小数量，实际上不需要交换元素，您只需要找到循环即可。 - MithunS

Answer 6

由于我们已经知道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

- user7188158

---

虽然这段代码可能解决了问题，但是包括解释它如何以及为什么解决问题将有助于提高您的帖子质量，可能会得到更多赞。请记住，您正在回答未来读者的问题，而不仅仅是现在问问题的人。请[编辑]您的答案以添加解释，并指出适用的限制和假设。 - double-beep

@double-beep，我已添加了描述。 - user7188158

Answer 7

@J.F. Sebastian和@Eyal Schneider的答案非常棒。 我受到启发，解决了一个类似的问题：计算排序数组所需的最小交换次数，例如：要对{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;
}

- spiralmoon

Answer 8

这似乎是一个编辑距离问题，只不过允许转位。

看看Damerau-Levenshtein距离的伪代码。我相信你可以调整它来仅计算转位。

- Nick Dandoulakis

---

我并不是很理解维基百科关于Damerau-Levenshtein算法的文章。就我所知，它提供的实现似乎并没有真正起作用：“事实上，该算法计算了所谓最优字符串对齐的成本，并不总是等于编辑距离。同时，我们也容易看出，在不超过一次编辑任何子字符串的情况下，最优字符串对齐的成本就是使字符串相等所需的编辑操作数。” - IVlad