我正在将一个没有相同数字的整数序列（不失一般性，假设该序列是 的排列1,2,...,n）排序为它的自然递增顺序（即1,2,...,n）。我正在考虑以最少的交换次数直接交换元素（无论元素的位置如何；换句话说，交换对任何两个元素都有效）（以下可能是一个可行的解决方案）：
交换两个元素，其中一个或两个元素应交换到正确的位置。直到每个元素都放在正确的位置。
但我不知道如何在数学上证明上述解决方案是否是最优的。任何人都可以帮忙吗？
问问题
28480 次
19 回答
71
我能够用图论证明这一点。可能想在 :) 中添加该标签
创建一个有n顶点的图。如果位置中的元素应该以n_i正确的顺序就位，则从节点创建一条边。您现在将拥有一个由几个非相交循环组成的图形。我认为正确排序图表所需的最小交换次数是n_jij
M = sum (c in cycles) size(c) - 1
花点时间说服自己……如果两个项目在一个循环中，一次交换就可以解决它们。如果三个项目在一个循环中，您可以交换一对以将一个放在正确的位置，然后剩下两个循环，等等。如果n项目在一个循环中，您需要n-1交换。（即使您不与直接邻居交换，这始终是正确的。）
鉴于此，您现在可能能够看到为什么您的算法是最优的。如果您进行交换并且至少一个项目位于正确的位置，那么它将始终将 的值减少M1。对于任何长度的循环n，请考虑将一个元素交换到正确的位置，由其邻居占据。您现在有一个正确排序的元素和一个长度循环n-1。
由于M是交换的最小数量，并且您的算法M每次交换总是减少 1，因此它必须是最优的。
于 2013-03-01T07:21:38.380 回答
24
所有的周期盘点都很难记住。有一种方法更容易记忆。
首先，让我们手动浏览一个示例案例。
- 序列：[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
因此，您不需要记住访问过的节点或计算一些周期长度。
于 2018-12-27T15:39:33.043 回答
6
供您参考，这是我编写的一种算法，用于生成对数组进行排序所需的最小交换次数。它找到@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;
}
于 2016-11-09T12:57:57.363 回答
6
我们不需要交换实际的元素，只需找出有多少元素不在正确的索引中（循环）。最小掉期为 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;
}
于 2019-03-17T11:20:11.513 回答
3
@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 有一个很好的观点。
于 2019-10-28T21:39:10.877 回答
2
斯威夫特 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
}
于 2018-08-13T11:50:50.693 回答
2
// 假设我们只处理从零开始的序列
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
}
于 2018-08-26T15:55:34.963 回答
2
我真的很喜欢@Ieuan Uys 在 Python 中的解决方案。
我对他的解决方案的改进；
- while循环少迭代一次以提高速度；
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] 交换。值3将在 a[3] 应该在的位置。一个值被发送到它的位置。我们还有 n-2 次迭代。我对现在的 a[0] 不感兴趣。如果在该位置不为 0，则稍后将其交换为另一个值。因为另一个值也存在于错误的地方，所以后面的while循环会识别出来。
真实例子
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.
于 2020-04-13T20:22:49.653 回答
1
@bekce 做得很好的解决方案。如果使用 C#，设置修改数组的初始代码ar可以简洁地表示为：
var origIndexes = Enumerable.Range(0, n).ToArray();
Array.Sort(ar, origIndexes);
然后在其余代码中使用origIndexes而不是。ar
于 2016-11-22T23:12:13.720 回答
0
这是 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;
}
于 2017-01-05T09:47:05.087 回答
0
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);
}
}
于 2019-01-15T09:31:31.170 回答
0
斯威夫特 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
}
于 2019-02-11T04:52:57.747 回答
0
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
于 2019-09-07T19:27:30.980 回答
0
在 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 代码
于 2019-10-17T10:19:27.100 回答
0
这是@Archibald 已经解释过的Java 解决方案。
static int minimumSwaps(int[] arr){
int swaps = 0;
int[] arrCopy = arr.clone();
HashMap<Integer, Integer> originalPositionMap
= new HashMap<>();
for(int i = 0 ; i < arr.length ; i++){
originalPositionMap.put(arr[i], i);
}
Arrays.sort(arr);
for(int i = 0 ; i < arr.length ; i++){
while(arr[i] != arrCopy[i]){
//swap
int temp = arr[i];
arr[i] = arr[originalPositionMap.get(temp)];
arr[originalPositionMap.get(temp)] = temp;
swaps += 1;
}
}
return swaps;
}
于 2019-12-14T15:14:41.267 回答
0
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
于 2020-04-04T07:02:02.043 回答
0
使用 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
于 2020-04-18T21:56:38.873 回答
0
苹果斯威夫特版本 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
}
于 2020-08-08T20:26:02.483 回答
0
找到排列 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
于 2021-05-09T11:04:29.570 回答