用最小的代价对排列进行排序

Question

给定一个元素排列 {1, 2, 3, ..., N}，需要使用交换操作将其排序。交换元素x和y的操作的成本为min(x,y)。

需要找出对排列进行排序的最小成本。我考虑贪心地从N到1遍历并使用交换操作将每个元素放在其位置上，但这不是一个好主意。

- user1359532

---

所以，我理解的问题是：你会得到一个排列。对于这个给定的排列，您需要使用具有每次交换成本的交换操作找到将其排序的最小成本？ - hyde

交换成本，X和Y元素是最终位置或值，还是它们当前所在的位置元素？ - hyde

这其实是个诡异的问题吗？如果成本是min(x,y)，那么你总是要和1交换...需要两次交换才能将元素放到正确的位置。 - hyde

@hyde - 不是的，考虑 [4,3,2,1] - 最优解是交换 (1,4) 和 (2,3)，代价为 3。 - dfb

@dfb 嗯，有一些特殊情况... 还有元素已经在正确位置的情况。大多数情况下每个元素只需要交换一次，而不是两次（将1与应该到达1所在位置的元素进行交换）。 - hyde

寻找操作被视为微不足道且唯一的成本是交换值，还是像传统排序算法一样进行分析，在这种情况下唯一的操作是交换？ - WLPhoenix

Answer 1

如果查找过程是琐碎的，那么最小交换次数将由循环的数量确定。这个原则类似于布谷鸟散列。你可以取排列中的第一个值，并查看原始索引处的值的索引处的值。如果它们匹配，则进行单个操作的交换。

[3 2 1] : 值3在索引1上，因此查看索引3上的值。 [3 2 1] : 值1在索引3上，因此存在两个索引的循环。交换这些值即可。

如果不是，则把第一个索引推到栈上并寻找第二个索引值的索引。最终会出现一个循环。此时，开始通过弹出栈上的值进行交换。这将需要n-1次交换，其中n为循环的长度。

[3 1 2]：值3在索引1，因此查看索引3的值。
[3 1 2]：值2在索引3，因此将3添加到堆栈中并寻求索引2。同时将3存储为循环的起始值。
[3 1 2]：值1在索引2，因此将2添加到堆栈中并寻求索引1。
[3 1 2]：值3是循环的开头，因此弹出堆栈中的2并交换值1和2。
[1 3 2]：将3从堆栈中弹出并交换2和3，从而得到带有2次交换的排序列表。
[1 2 3]

使用此算法，最大交换次数将是N-1，其中N是值的总数。当存在N长度的循环时会发生这种情况。

编辑：此算法给出了最小的交换次数，但不一定使用min(x, y)函数得到最小值。我没有计算，但我认为swap(x, y) = {swap(1, x), swap(1, y), swap(1, x)} 应该仅在x属于{2，3}且n < 2时不使用；很容易将其写成特殊情况。最好检查并显式地放置2和3，然后按照评论中提到的算法进行两次操作的排序。

编辑2：相信这将捕获所有情况。

while ( unsorted ) {
    while ( 1 != index(1) )
        swap (1 , index (1) )

    if (index(2) == value@(2))
        swap (2, value@(2) )

    else
        swap (1 , highest value out of place)
}

- WLPhoenix

---

由于某种原因，它不允许我进行编辑，但是该条件语句应该包括只有2和value@(2)是不正确的值。 - WLPhoenix

Answer 2

这是否最优选择：

Find element 2
If it is not at correct place already

    Find element at position 2
    If swapping that with 2 puts both to right place

        Swap them
        Cost = Cost + min(2, other swapped element)

repeat

   Find element 1
   If element 1 is at position 1

      Find first element that is in wrong place
      If no element found

          set sorted true

      else

         Swap found element with element 1
         Cost = Cost + 1

   else

      Find element that should go to the position where 1 is
      Swap found element with element 1
      Cost = Cost + 1

until sorted is true

- hyde

---

我对这个算法的疑虑是：1.首先处理2是否可行，或者在循环的中间某处通过某些条件来处理它会更好？2.当1最终到达自己的位置时，选择与1交换的错误元素是否重要？ - hyde

@WLPhoenix 好的好的，我已经替换了goto语句，甚至没有使用break。满意吗？ ;) - hyde

Answer 3

嗯，一个有趣的问题。我脑海里浮现出来的一个快速算法是使用元素作为索引。我们首先找到值为1的元素的索引，并将其与该数字的元素交换。最终，这将导致1出现在第一个位置，这意味着您必须将1与尚未处于正确位置的某个元素交换并继续。这个算法在排列（2、3、...、N、1）的情况下的下限为N-1，但确切的成本会有所变化，最高可达2 * N-2。

好的，考虑到上述算法和示例，我认为最优秀的方法是通过不断地用任何元素交换1直到它首先到达第一位，然后如果它还没有在正确的位置上，就将2与第二位交换，然后继续用尚未处于正确位置的任何内容交换1，直到排序完成。

set sorted=false
while (!sorted) {
    if (element 1 is in place) {
        if (element 2 is in place) {
            find any element NOT in place
            if (no element found) sorted=true 
            else {
                swap 1 with element found
                cost++
            }
        } else {
            swap 2 with element at second place
            cost+=2
        }
    } else {
        find element with number equals to position of element 1
        swap 1 with element found
        cost++
    }
}

- Vesper

---

观察实际问题评论中的示例[4,3,2,1]，最优成本为3，仅使用1进行交换无法达到此目标，因此正确的算法需要更加复杂。 - hyde

好的，一个反例[2,3,1]，使用你的算法，最终结果是3，而用我的算法则是2 - 先将1和3交换，然后再将1和2交换。 - Vesper

是的，我怀疑整个算法需要更加复杂，但我认为我会稍微改变我的版本，使其同时覆盖[4,3,2,1]和[2,3,1]。 - hyde

问题仍然基于数字循环。如果2在一个2索引循环中，那么单个交换总是最有效的。否则，最好将1交换到循环中，并让它完全通过循环过滤，然后重复此过程。 - WLPhoenix

Answer 4

如果你有数字 1、2、...、N 的排列，那么排序后的集合将恰好是 1、2、...、N。因此，你可以在O(0)的复杂度下知道答案（即根本不需要算法）。

---

如果你想通过重复交换来排序范围，你可以反复进行“推进和循环”操作：推进已经排序好的范围（其中 a[i] == i），然后将a[i]与a[a[i]]交换，直到完成循环为止。重复此过程，直到达到末尾。这最多需要 N - 1 次交换，并基本上执行排列的循环分解。

- Kerrek SB

---

OP需要找到成本。 - dfb

我认为这个问题是计算从排列到{1, 2, ..., N}所需的最小交换次数。 - kennytm

@dfb 成本为零。但是，我认为 OP 没有正确表达自己。 - A E

@japreiss确实，如果排列已经排序，则实际最小值仍为0。这需要OP进行一些解释，因为问题听起来像是要求任何排列的最低最大成本算法。所以也许我们只是感到困惑。 - Vesper

看起来我的算法符合这个任务的要求... 在上面Hyde的回答中有更详细的解释。 - Vesper

Answer 5

使用桶排序，桶大小为1。
成本为零，因为没有交换发生。 现在通过桶数组进行一次遍历，并将每个值交换回原始数组中的相应位置。
这是N次交换。
N的总和为N（N+1）/2，给您一个确切的固定成本。

另一种解释是，您只需从桶数组中存储回原始数组即可。那就没有交换，因此成本为零，这是一个合理的最小值。

- EvilTeach