计算最小数量的交换以订购序列

Question

我正在研究一个整数序列,它没有相同的数字(不失一般性,让我们假设序列是一个排列1,2,...,n)到它的自然递增顺序(即1,2,...,n).我正在考虑直接交换元素(无论元素的位置如何;换句话说,交换对任何两个元素都有效),交换次数最少(以下可能是一个可行的解决方案):

交换两个元素的约束条件是应将其中一个或两个交换到正确的位置.直到每个元素都放在正确的位置.

但我不知道如何在数学上证明上述解决方案是否是最优的.有人可以帮忙吗？

Answer 1

我能用图论来证明这一点.可能想在:)中添加该标签

创建带n顶点的图形.创建一个从节点的边n_i来n_j,如果在位置的元素i应该在的位置j在正确的顺序.现在,您将拥有一个由几个非交叉循环组成的图形.我认为正确订购图表所需的最小交换次数是

M = sum (c in cycles) size(c) - 1

花一点时间来说服自己...如果两个物品在一个周期中,一个交换就可以照顾它们.如果一个循环中有三个项目,您可以交换一对以将其中一个放在正确的位置,并保留两个循环等.如果n项目处于循环中,则需要n-1交换.(即使你不与邻居交换也是如此.)

鉴于此,您现在可以看到为什么您的算法是最优的.如果进行交换并且至少有一个项位于正确位置,那么它将始终将值减小M1.对于任何长度循环n,请考虑将元素交换到由其邻居占用的正确位置.您现在拥有一个正确排序的元素和一个长度循环n-1.

由于M交换的最小数量,并且M每个交换的算法总是减少1,因此它必须是最优的.

Answer 2

嗯，所有循环计数都很难掌握。有一种方法更容易记住。

首先，让我们手动扔一个样品盒。

• 顺序：[7、1、3、2、4、5、6]
• 枚举它：[（ 0，7 ），（1，1），（2，3），（3，2），（4，4），（5，5），（6，6）]
• 按值对枚举进行排序：[（1，1），（3，2），（2，3），（4，4），（5，5），（6，6），（0，7）]
• 从头开始。虽然索引与枚举索引不同，但请继续交换由索引和枚举索引定义的元素。请记住：swap(0,2);swap(0,3)与swap(2,3);swap(0,2)
  • swap(0, 1)=> [ （3，2），（1，1），（2，3），（4，4），（5，5），（6，6），（0，7）]
  • swap(0, 3)=> [ （4，4），（1，1），（2，3），（3，2），（5，5），（6，6），（0，7）]
  • swap(0, 4)=> [ （5，5），（1，1），（2，3），（3，2），（4，4），（6，6），（0，7）]
  • swap(0, 5)=> [ （6，6），（1，1），（2，3），（3，2），（4，4），（5，5），（0，7）]
  • swap(0, 6)=> [ （0，7），（1，1），（2，3），（3，2），（4，4），（5，5），（6，6） ]

也就是说，从语义上说，您对元素进行排序，然后找出如何通过交换不适当的最左边的项目将它们置于初始状态。

Python算法很简单：

def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp


def minimum_swaps(arr):
    annotated = [*enumerate(arr)]
    annotated.sort(key = lambda it: it[1])

    count = 0

    i = 0
    while i < len(arr):
        if annotated[i][0] == i:
            i += 1
            continue
        swap(annotated, i, annotated[i][0])
        count += 1

    return count

因此，您不需要记住访问的节点，也不需要计算一些周期长度。

Answer 3

供您参考,这是我编写的算法,用于生成排序数组所需的最小交换次数.它找到了@Andrew Mao所描述的周期.

/**
 * Finds the minimum number of swaps to sort given array in increasing order.
 * @param ar array of <strong>non-negative distinct</strong> integers. 
 *           input array will be overwritten during the call!
 * @return min no of swaps
 */
public int findMinSwapsToSort(int[] ar) {
    int n = ar.length;
    Map<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < n; i++) {
        m.put(ar[i], i);
    }
    Arrays.sort(ar);
    for (int i = 0; i < n; i++) {
        ar[i] = m.get(ar[i]);
    }
    m = null;
    int swaps = 0;
    for (int i = 0; i < n; i++) {
        int val = ar[i];
        if (val < 0) continue;
        while (val != i) {
            int new_val = ar[val];
            ar[val] = -1;
            val = new_val;
            swaps++;
        }
        ar[i] = -1;
    }
    return swaps;
}

Answer 4

我们不需要交换实际的元素，只需找出有多少元素不在正确的索引（Cycle）中。最小交换次数为 Cycle - 1；这是代码...

static int minimumSwaps(int[] arr) {
        int swap=0;
        boolean visited[]=new boolean[arr.length];

        for(int i=0;i<arr.length;i++){
            int j=i,cycle=0;

            while(!visited[j]){
                visited[j]=true;
                j=arr[j]-1;
                cycle++;
            }

            if(cycle!=0)
                swap+=cycle-1;
        }
        return swap;


    }