浙大PAT-Sort with Swap(0, i)

算法

来自ZJU数据结构基础的习题。

Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:
Each input file contains one test case, which gives a positive N(≤105) followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.

Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:
10
3 5 7 2 6 4 9 0 8 1

Sample Output:
9

题目意思是，给定一串由0,1,2,…,N-1重新排列而成的数，只通过交换0与某一个数这样的操作，最后将数列排列为0,1,2,…,N-1。让你编一个程序，接收给定的数列，输出排列结束所需最少的交换次数。C++代码我放在最后，这里撇开程序，集中讨论解决这个问题的方法。

设$a_0,a_1,a_2,…,a_{n-1}$是$0,1,2,…,n-1$的一个置换，交换0与$a_i$称为一次交换操作，下面将给出把$a_0,a_1,a_2,…,a_{n-1}$利用交换操作变成$0,1,2,…,n-1$所需的最小操作次数以及具体方法。

用表格记录置换如下：

把表格中规定的对应关系记为$f$，那么$f$给出了0到$n-1$的一个置换。

现在对于$k$，构造数据链$\{k_s\}$，$k_0=k$，$k_{s+1}=f(k_s)$，那么容易发现，这是一条周期链，且在同一个周期内无重复元素。记最小正周期为$T(k)$，就是说数据$k_0,k_1,…,k_{T(k)-1}$构成一个圆环，环中元素互不相同，$k_{s+1}=f(k_s)$且$k_0=f(k_{T(k)-1})$。不仅如此，定义一个关系~，如果a,b同属于某个链$\{k_s\}$，那么$a$~$b$。可以证明，~是一个等价关系。数据0到$n-1$被~分成了许多等价类。

举个例子：现在$n=10$，数据列为3 5 7 2 6 4 9 0 8 1 （就是示例），按上面的描述，可以填出表格：

从0开始构造数据链：

0->3->2->7->(0)
1->5->4->6->9->(1)
8->(8)

在同一个链中的元素，就认为是互相等价的。那么在此例中，0到$n-1$，就被分成了3个等价类。从单个的意义来说，等价类的各个元素都完全对称。

现在我们从等价类的角度来看一般的交换操作。设swap(i,j)表示交换数据$i$,$j$的操作，具体到表格中就是交换$i$与$j$的值。假设$i$与$j$同属一个等价类，那么不难证明，交换之后链被分成两个（分别含有$i$和$j$的链），例如1->5->4->6->9->(1)中，交换1和6，那么新的$f(1)$为原来的$f(6)$，即9，所以包含1的链为1->9->(1)，类似地，包含6的链为6->5->4->(6)。如果$i$与$j$不属一个等价类，那么不难证明，swap(i,j)导致两条链合并成一条。例如0->3->2->7->(0)与1->5->4->6->9->(1)，交换7和5，链变成7->4->6->9->1->5->0->3->2->(7)。

我们最终的目的，是要通过0与其他元素的交换，将0到$n-1$分成$n$个互不相同的等价类。具体到本题，我们需要关注等价类中的两个性质，一是有没有0，二是环中元素共多少个。为了把一个长度为$S$($S>1$)(这里的长度指的是链的周期)的、不含0的链分成$S$个链，我们至少需要进行$S+1$次交换操作，即将0所在链与其合并得到一个长度至少为$S+1$的链，然后进行至少$S$次断链操作。而对于0所在长度为$S$的链，至少需要$S-1$次断链操作才能分成$S$个等价类。这样一来，我们就得到最小操作次数的一个下界。

事实上这个下界可以用这样的方法取到：将0所在链断成若干个单元素等价类，然后将0元素与其他非单元素链合并，再重复上述操作，除非找不到其他单元素链，这时任务完成。实际上，这就是代码所蕴含的思路。

以示例为例：

0->3->2->7->(0)
1->5->4->6->9->(1)
8->(8)

交换0与3（交换1次），得到

0->2->7->(0)
1->5->4->6->9->(1)
8->(8)
3->(3)

依次交换0与2,7（累计交换3次），得到

0->(0)
1->5->4->6->9->(1)
8->(8)
3->(3)
2->(2)
7->(7)

也就是说，依次将0与$f(0)$,$f(f(0))$,…直到0的元素进行交换，可以把0所在链给完全断开。

交换0与1（累计交换4次），得到

0->5->4->6->9->1->(0)
8->(8)
3->(3)
2->(2)
7->(7)

这一操作把单元素链0与其他非单元素链组合起来。

再依次交换0与5,4,6,9,1（累计交换9次），即可完成任务。这样一来，交换次数为9，即为所求。

下面是该问题的C++代码解，时间和空间复杂度都是O(n)。注释我就没写了，因为网上可以搜到相同思路的代码，只是没有像上面一样给出一个比较完善的证明。

#include <iostream>
using namespace std;
int search(int* p, int num)
{
    static int first = 1;
    for (int i = first; i<num; i++)
        if (p[i] != i)
            return first = i;
    return 0;
}
void swap(int* p, int n)
{
    int temp = p[0];
    p[0] = p[n];
    p[n] = temp;
}
int main()
{
    int n;
    cin >> n;
    int *data = new int[n];
    int temp;
    for (int i = 0; i<n; i++)
    {
        cin >> temp;
        data[temp] = i;
    }
    int count = 0;
    while (true)
    {
        if (data[0])
            swap(data, data[0]);
        else
        {
            temp = search(data, n);
            if (!temp) break;
            swap(data, temp);
        }
        count++;
    }
    cout << count << endl;
    delete[] data;
    return 0;
}