计算最小交换次数以订购序列 [英] 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 n_i 到 n_j 的边$ c>应该以正确的顺序放在 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。对于任何长度为<$ c $的周期c> 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屋！