计算最少的交换次数以订购一个序列

Question

以前我曾经对没有相同数字的整数序列进行排序（不失一般性，让我们假设序列是1,2,...,n的排列）到其自然递增顺序（即1,2,...,n） 。我想到了如何交换元素（无论元素的位置如何，换句话说，交换对于任何两个元素都是有效的），并且交换次数最少。我想以下是一个可行的算法：

交换两个元素的约束，其中一个或两个应交换到正确的位置（S）。直到每个元素都处于正确的位置。

但我不知道如何在数学上证明上述算法是否可以导致最优解。任何人都可以帮忙

非常感谢。

Answer 1

我可以用图论证明这一点。可能要添加标签的:)

与n顶点创建一个图表。如果位置i中的元素应位于j的正确顺序中，请创建从节点n_i到n_j的边。现在您将有一个由几个非相交循环组成的图。我认为，需要订购的图形交换的最小数量是正确

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

花一秒钟去说服那自己......如果两个项目是在一个周期内，一个是swap可以只照顾他们。如果三个项目在一个周期中，您可以交换一对以将其中一个放在正确的位置，剩下两个周期等。如果n项目处于周期中，则需要n-1交换。 （这始终是真实的，即使你不近邻交换。）

鉴于这种情况，你现在也许可以明白为什么你的算法是最优的。如果您进行了交换并且至少有一个项目位于正确的位置，那么它总是会将M的值减少1.对于任何长度为n的循环，请考虑将元素交换到由其邻居占用的正确位置。您现在有一个正确的有序元素，并且有一个长度为n-1的周期。

由于M是交换的最小次数，并且您的算法每次交换总是将M减1，因此它必须是最优的。

Answer 2

为了供您参考，以下是我编写的算法，用于生成排序数组所需的最小交换次数。它找到@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 3

由@bekce完成的解决方案。如果使用C＃，设置修改后的数组ar的初始代码可以简洁地表述为：

var origIndexes = Enumerable.Range(0, n).ToArray(); 
Array.Sort(ar, origIndexes); 

然后在代码的其余部分使用origIndexes代替ar。

Answer 4

这是C++的示例代码，查找互换的最小数量排序的(1,2,3,4,5,.......n-2,n-1,n)

#include<bits/stdc++.h> 
using namespace std; 


int main() 
{ 
    int n,i,j,k,num = 0; 
    cin >> n; 
    int arr[n+1]; 
    for(i = 1;i <= n;++i)cin >> arr[i]; 
    for(i = 1;i <= n;++i) 
    { 
     if(i != arr[i])// condition to check if an element is in a cycle r nt 
     { 
      j = arr[i]; 
      arr[i] = 0; 
      while(j != 0)// Here i am traversing a cycle as mentioned in 
      {    // first answer 
       k = arr[j]; 
       arr[j] = j; 
       j = k; 
       num++;// reducing cycle by one node each time 
      } 
      num--; 
     } 
    } 
    for(i = 1;i <= n;++i)cout << arr[i] << " ";cout << endl; 
    cout << num << endl; 
    return 0; 
}