置换环算法

置换环算法

——2023.05.22

这是由abc302—G所带来新的算法学习——置换环
虽然但是我还是没弄懂G是怎么写的，烦死啦

置换环的作用

• 求出通过交换数组的元素的最少次数，来得到按照某种指定规则进行排序的数组

核心思想

• 将每个位置(i)上的元素指向它本应该在的位置(j)，即连一条有向边<i,j>
• 这样一来，每个位置都处在环上(如果某个位置上的数指向自己，那么这个位置自环)
• 手玩(手动模拟)一下就可以知道，每个环中的交换次数最少为 环内点数 - 1
• 数组的最小交换次数 = Σ(每个环)(环内点数 - 1) = 数组大小 - 环的数量
  

理解

为什么每个位置一定处在环上呢？

我们以每个位置的出度和入度为切入点进行分析。

∵ 数组的每个位置(i)上都存在一个数，而这个数，一定有一个它本应该处在的位置(j),
   按照置换环的核心思想，我们应该连一条<i,j>

∴ 每个位置的出度为 1

∵ 每个位置(i)都一定属于某个位置(k)上的数
   按照置换环的核心思想，我们应该连一条<k,i>

∴ 每个位置的入度为 1

综上所述，每个位置的入度和出度分别为 1，总度数为 2

现假设存在一个位置不在环上

那么这个位置一定存在于链上，而链的端点要么入度为 1，要么出度为 1，与上述结论矛盾，所以假设不成立

所以 每个位置一定处在环上

为什么一定要在环内进行交换操作才能得到最小交换次数呢？

我的理解是，环其实代表的其实是一种范围

如果 环i中的点 和 环j中的点 交换，不仅无效，而且可能会造成更坏的结果

因为每个位置i指向的位置j都是环内的点，所以我们只需要摆正环内的位置即可

所以我们应该在环内进行交换