计算排序序列的最小交换次数 [英] Compute the minimal number of swaps to order a sequence

问题描述

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

I'm working on sorting an integer sequence with no identical numbers (without loss of generality, let's assume the sequence is a permutation of 1,2,...,n) into its natural increasing order (i.e. 1,2,...,n). I was thinking about directly swapping the elements (regardless of the positions of elements; in other words, a swap is valid for any two elements) with minimal number of swaps (the following may be a feasible solution):

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

Swap two elements with the constraint that either one or both of them should be swapped into the correct position(s). Until every element is put in its correct position.

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

But I don't know how to mathematically prove if the above solution is optimal. Anyone can help?

推荐答案

我能够用 图论.可能想在 :)

I was able to prove this with graph-theory. Might want to add that tag in :)

创建一个具有 n 个顶点的图.如果位置 i 中的元素应该在正确的位置 j 中，则创建从节点 n_i 到 n_j 的边订购.您现在将拥有一个由几个不相交的循环组成的图形.我认为正确排序图形所需的最小交换次数是

Create a graph with n vertices. Create an edge from node n_i to n_j if the element in position i should be in position j in the correct ordering. You will now have a graph consisting of several non-intersecting cycles. I argue that the minimum number of swaps needed to order the graph correctly is

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

花点时间说服自己...如果两个项目在一个循环中，一次交换就可以解决它们.如果三个项目在一个循环中，你可以交换一对把一个放在正确的位置，剩下一个两个循环，等等.如果n个项目在一个循环中，你需要n-1 交换.(即使您不与直接邻居交换，这始终是正确的.)

Take a second to convince yourself of that...if two items are in a cycle, one swap can just take care of them. If three items are in a cycle, you can swap a pair to put one in the right spot, and a two-cycle remains, etc. If n items are in a cycle, you need n-1 swaps. (This is always true even if you don't swap with immediate neighbors.)

考虑到这一点，您现在可能会明白为什么您的算法是最佳的.如果你做一个交换并且至少有一项在正确的位置，那么它总是将 M 的值减少 1.对于任何长度为 n 的循环，考虑将一个元素交换到正确的位置，由它的邻居占据.您现在有一个正确排序的元素和一个长度为 n-1 的循环.

Given that, you may now be able to see why your algorithm is optimal. If you do a swap and at least one item is in the right position, then it will always reduce the value of M by 1. For any cycle of length n, consider swapping an element into the correct spot, occupied by its neighbor. You now have a correctly ordered element, and a cycle of length n-1.

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

Since M is the minimum number of swaps, and your algorithm always reduces M by 1 for each swap, it must be optimal.

这篇关于计算排序序列的最小交换次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！