计算对序列进行排序的最小交换次数

我能够用图论证明这一点。可能希望在 :) 中添加该标记

创建带有顶点的图形。创建从节点到位置的边，如果位置中的元素应按正确的顺序就位。现在，您将拥有一个由几个不相交的循环组成的图形。我认为正确排序图形所需的最小交换次数是nn_in_jij

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

花点时间说服自己......如果两个项目在一个循环中，一个交换可以处理它们。如果一个周期中有三件物品，您可以交换一对将一对放在正确的位置，然后剩下两个周期，依此类推。如果物品处于一个周期中，则需要交换。（即使您不与近邻交换，也始终如此。nn-1

鉴于此，您现在可能能够看到为什么您的算法是最佳的。如果您进行交换并且至少有一个项目处于正确的位置，那么它将始终将 的值减少 1。对于任何长度的循环，考虑将元素交换到正确的位置，由其相邻元素占据。您现在有一个正确排序的元素，以及一个长度为 的循环。Mnn-1

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

供您参考，这是我编写的一个算法，用于生成对数组进行排序所需的最小交换次数。它找到@Andrew 毛描述的周期。

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

@bekce做得很好的解决方案。如果使用 C#，则设置修改后的数组的初始代码可以简洁地表示为：ar

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

然后在代码的其余部分使用 instead 而不是。origIndexesar

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

Swift 4 版本：

func minimumSwaps(arr: [Int]) -> Int {

      struct Pair {
         let index: Int
         let value: Int
      }

      var positions = arr.enumerated().map { Pair(index: $0, value: $1) }
      positions.sort { $0.value < $1.value }
      var indexes = positions.map { $0.index }

      var swaps = 0
      for i in 0 ..< indexes.count {
         var val = indexes[i]
         if val < 0 {
            continue // Already visited.
         }
         while val != i {
            let new_val = indexes[val]
            indexes[val] = -1
            val = new_val
            swaps += 1
         }
         indexes[i] = -1
      }
      return swaps
}

假设我们只处理从零开始的序列

function minimumSwaps(arr) {
    var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start) {
                j = arr[j]
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

所有的周期计数都很难记在你的脑海里。有一种方法更容易记住。

首先，让我们手动浏览一个示例案例。

• 序列：[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):
    arr[i], arr[j] = arr[j], arr[i]


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

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

Java 中具有基元类型的整数实现（和测试）。

import java.util.Arrays;

public class MinSwaps {
  public static int computate(int[] unordered) {
    int size = unordered.length;
    int[] ordered = order(unordered);
    int[] realPositions = realPositions(ordered, unordered);
    boolean[] touchs = new boolean[size];
    Arrays.fill(touchs, false);
    int i;
    int landing;
    int swaps = 0;

    for(i = 0; i < size; i++) {
      if(!touchs[i]) {
        landing = realPositions[i];

        while(!touchs[landing]) {
          touchs[landing] = true;
          landing = realPositions[landing];

          if(!touchs[landing]) { swaps++; }
        }
      }
    }

    return swaps;
  }

  private static int[] realPositions(int[] ordered, int[] unordered) {
    int i;
    int[] positions = new int[unordered.length];

    for(i = 0; i < unordered.length; i++) {
      positions[i] = position(ordered, unordered[i]);
    }

    return positions;
  }

  private static int position(int[] ordered, int value) {
    int i;

    for(i = 0; i < ordered.length; i++) {
      if(ordered[i] == value) {
        return i;
      }
    }

    return -1;
  }

  private static int[] order(int[] unordered) {
    int[] ordered = unordered.clone();
    Arrays.sort(ordered);

    return ordered;
  }
}

测试

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class MinimumSwapsSpec {
  @Test
  public void example() {
    // setup
    int[] unordered = new int[] { 40, 23, 1, 7, 52, 31 };

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(5, minSwaps);
  }

  @Test
  public void example2() {
    // setup
    int[] unordered = new int[] { 4, 3, 2, 1 };

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(2, minSwaps);
  }

  @Test
  public void example3() {
    // setup
    int[] unordered = new int[] {1, 5, 4, 3, 2};

    // run
    int minSwaps = MinSwaps.computate(unordered);

    // verify
    assertEquals(2, minSwaps);
  }
}

Swift 4.2：

func minimumSwaps(arr: [Int]) -> Int {
    let sortedValueIdx = arr.sorted().enumerated()
        .reduce(into: [Int: Int](), { $0[$1.element] = $1.offset })

    var checked = Array(repeating: false, count: arr.count)
    var swaps = 0

    for idx in 0 ..< arr.count {
        if checked[idx] { continue }

        var edges = 1
        var cursorIdx = idx
        while true {
            let cursorEl = arr[cursorIdx]
            let targetIdx = sortedValueIdx[cursorEl]!
            if targetIdx == idx {
                break
            } else {
                cursorIdx = targetIdx
                edges += 1
            }
            checked[targetIdx] = true
        }
        swaps += edges - 1
    }

    return swaps
}

我们不需要交换实际的元素，只需找出有多少元素不在正确的索引（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;


    }

Python 代码

A = [4,3,2,1]
count = 0
for i in range (len(A)):
    min_idx = i
    for j in range (i+1,len(A)):
        if A[min_idx] > A[j]:
            min_idx = j
    if min_idx > i:
        A[i],A[min_idx] = A[min_idx],A[i]
        count = count + 1
print "Swap required : %d" %count

在 Javascript 中

如果数组的计数以 1 开头

function minimumSwaps(arr) {
   var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start + 1) {
                j = arr[j] - 1
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

else 表示以 0 开头的输入

function minimumSwaps(arr) {
    var len = arr.length
    var visitedarr = []
    var i, start, j, swap = 0
    for (i = 0; i < len; i++) {
        if (!visitedarr[i]) {
            start = j = i
            var cycleNode = 1
            while (arr[j] != start) {
                j = arr[j]
                visitedarr[j] = true
                cycleNode++
            }
            swap += cycleNode - 1
        }
    }
    return swap
}

只是为当前的 HackerEarth 输入扩展了 Darshan Puttaswamy 代码

@Archibald，我喜欢你的解决方案，这就是我最初的假设，即对数组进行排序是最简单的解决方案，但我认为没有必要像我所说的那样进行反向遍历，即枚举然后对数组进行排序，然后计算枚举的交换。

我发现从数组中的每个元素中减去 1 然后计算对该列表进行排序所需的交换更简单

这是我的调整/解决方案：

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

def minimum_swaps(arr):

    a = [x - 1 for x in arr]

    swaps = 0
    i = 0
    while i < len(a):
        if a[i] == i:
            i += 1
            continue
        swap(a, i, a[i])
        swaps += 1

    return swaps

至于证明最优性，我认为@arax说得有道理。

def swap_sort(arr)
  changes = 0
  loop do
    # Find a number that is out-of-place
    _, i = arr.each_with_index.find { |val, index| val != (index + 1) }
    if i != nil
      # If such a number is found, then `j` is the position that the out-of-place number points to.
      j = arr[i] - 1

      # Swap the out-of-place number with number from position `j`.
      arr[i], arr[j] = arr[j], arr[i]

      # Increase swap counter.
      changes += 1
    else
      # If there are no out-of-place number, it means the array is sorted, and we're done.
      return changes
    end
  end
end                                                                                                

我真的很喜欢 Python 中 @Ieuan Uys 的解决方案。

我对他的解决方案进行了哪些改进;

• 而循环则少迭代一次以提高速度;while i < len(a) - 1
• 交换函数被解封装，成为一个单一的功能。
• 添加了大量的代码注释以提高可读性。

我的 python 代码。

def minimumSwaps(arr):
    #make array values starting from zero to match index values. 
    a = [x - 1 for x in arr] 

    #initialize number of swaps and iterator.
    swaps = 0
    i = 0

    while i < len(a)-1:
        if a[i] == i:
            i += 1
            continue

        #swap.
        tmp = a[i] #create temp variable assign it to a[i]
        a[i] = a[tmp] #assign value of a[i] with a[tmp]
        a[tmp] = tmp #assign value of a[tmp] with tmp (or initial a[i])

        #calculate number of swaps.
        swaps += 1

    return swaps

详细说明代码在大小为 n 的数组上做什么;

我们逐个检查数组中除最后一个值（n-1 次迭代）之外的每个值。如果该值与数组索引不匹配，则我们将此值发送到索引值等于其值的位置。例如，如果在 a[0] = 3。然后这个值应该换成 a[3]。a[0] 和 a[3] 互换。值将位于它应该在的 a[3] 处。一个值被发送到它的位置。我们还剩下 n-2 次迭代。我对现在的 a[0] 不感兴趣。如果该位置不是 0，则将换成另一个值。因为另一个值也存在于错误的位置，所以 while 循环 latter 会识别它。3

真实例子

a[4, 2, 1, 0, 3]
#iteration 0, check a[0]. 4 should be located at a[4] where the value is 3. Swap them. 
a[3, 2, 1, 0, 4] #we sent 4 to the right location now.  
#iteration 1, check a[1]. 2 should be located at a[2] where the value is 1. Swap them. 
a[3, 1, 2, 0, 4] #we sent 2 to the right location now.  
#iteration 2, check a[2]. 2 is already located at a[2]. Don't do anything, continue. 
a[3, 1, 2, 0, 4] 
#iteration 3, check a[3]. 0 should be located at a[0] where the value is 3. Swap them. 
a[0, 1, 2, 3, 4] #we sent 0 to the right location now.  
# There is no need to check final value of array. Since all swaps are done. 

使用 Javascript 的解决方案。

首先，我设置了所有需要排序的元素及其当前索引，然后我遍历映射以仅对需要交换的元素进行排序。

function minimumSwaps(arr) {
  const mapUnorderedPositions = new Map()
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== i+1) {
      mapUnorderedPositions.set(arr[i], i)
    }
  }

  let minSwaps = 0
  while (mapUnorderedPositions.size > 1) {
    const currentElement = mapUnorderedPositions.entries().next().value
    const x = currentElement[0]
    const y = currentElement[1]

    // Skip element in map if its already ordered
    if (x-1 !== y) {
      // Update unordered position index of swapped element
      mapUnorderedPositions.set(arr[x-1], y)

      // swap in array
      arr[y] = arr[x-1]
      arr[x-1] = x

      // Increment swaps
      minSwaps++
    }

    mapUnorderedPositions.delete(x)
  }


  return minSwaps
}

如果您有类似 7 2 4 3 5 6 1 的输入，则调试将按以下方式进行：

Map { 7 => 0, 4 => 2, 3 => 3, 1 => 6 }
currentElement [ 7, 0 ]
swapping 1 with 7
[ 1, 2, 4, 3, 5, 6, 7 ]

currentElement [ 4, 2 ]
swapping 3 with 4
[ 1, 2, 3, 4, 5, 6, 7 ]

currentElement [ 3, 2 ]
skipped

minSwaps = 2

Apple Swift 版本 5.2.4

func minimumSwaps(arr: [Int]) -> Int {
    var swapCount = 0
    var arrayPositionValue = [(Int, Int)]()
    var visitedDictionary = [Int: Bool]()
    
    for (index, number) in arr.enumerated() {
        arrayPositionValue.append((index, number))
        visitedDictionary[index] = false
    }
    
    arrayPositionValue = arrayPositionValue.sorted{ $0.1 < $1.1 }

    for i in 0..<arr.count {
        var cycleSize = 0
        var visitedIndex = i

        while !visitedDictionary[visitedIndex]! {
            visitedDictionary[visitedIndex] = true
            visitedIndex = arrayPositionValue[visitedIndex].0
            cycleSize += 1
        }

        if cycleSize > 0 {
            swapCount += cycleSize - 1
        }
    }

    return swapCount
}

找到将 1..N 的排列排列顺序所需的最小交换次数。

我们可以使用它，我们知道排序结果是什么：1..N，这意味着我们实际上不必进行交换，只需计算它们。

1..N 的洗牌称为排列，由不相交的循环排列组成，例如，1..6 的这种排列：

1 2 3 4 5 6
6 4 2 3 5 1

由循环排列 （1,6）（2,4,3）（5） 组成

1->6(->1) cycle: 1 swap
2->4->3(->2) cycle: 2 swaps
5(->5) cycle: 0 swaps

因此，k 个元素的循环需要 k-1 交换才能整理好。

由于我们知道每个元素“属于”的位置（即值 k 属于位置 k-1），因此我们可以很容易地遍历循环。从 0 开始，我们得到 6，属于 5， 在那里，我们找到了 1，它属于 0，我们又回到了起点。

为了避免以后重新计算周期，我们会跟踪访问了哪些元素 - 或者，您可以执行交换，以便在以后访问它们时这些元素位于正确的位置。

生成的代码：

def minimumSwaps(arr):
    visited = [False] * len(arr)
    numswaps = 0
    for i in range(len(arr)):
        if not visited[i]:
            visited[i] = True
            j = arr[i]-1
            while not visited[j]:
                numswaps += 1
                visited[j] = True
                j = arr[j]-1
    return numswaps

Go 版本 1.17：

func minimumSwaps(arr []int32) int32 {

var swap int32
for i := 0; i < len(arr) - 1; i++{
    for j := 0; j < len(arr); j++ {
        if arr[j] > arr[i] {
            arr[i], arr[j] = arr[j], arr[i]
            swap++
        }else {
        continue
    }
    }
} 
return swap
}