作者: 肖追日(西交) & 戴云舒(21级数院)

引言

看到标题其实就差不多知道本篇有趣的小题可能和高数线代的内容会有亿点点的不同.并且针对人群差不多也就是学习抽代的同学以及信息类学习算法的同学.但是我们也会尽量以通俗的语言,对涉及到的一些前置知识进行简单的介绍,如果还是不能够理解也没有关系,就当那种看了也昏昏欲睡的科普内容就行,毕竟考试考到这种内容应该还算比较少见的🤗.

而且我鼓励大家可以在看正式的分析内容之前,可以自己先用一两个小时的时间进行思考(不管是什么专业),看你是否有独特的想法!!!而问题的来源则是两位作者之间的聊天:

当然再追溯一下原问题的话则可以见:->【原题链接】<-

作为不同专业的人,西交友好市民,常年与计算机打交道的肖先生是从简易图论的想法出发,而经常和抽象打交道的戴某人,便是从更抽象的角度出发进行思考.但是敏锐的同学或许能够发现这两种方式背后原理的高度相似性!熟悉抽代的人可能知道这个名词----这就是一种不太严谨的同构关系!😃

因此大家也可以从本文中看到不同的人对同一个问题的不同思考方式,我总觉得这是很有趣的一件事,并且比内容本身更重要.

如果知道以下知识可能更容易理解: 抽象代数对称群(文中也会简单的介绍一遍的)

适合人群: 学习抽代的同学或者信息类的同学(但是大家都可以去学习学习分析问题的方法)

后续我们也会不定时推送有趣的小题系列,并且更偏向于数学学习过程中涉及到的概念和知识点的巩固与深入,感兴趣的同学可以多多关注!

Xzr的思路与想法

『题目简述』

定义：称一个的排列是简洁的，当且仅当均满足：或者，其中表示第的位置处的取值。

现在给你一个任意的的排列，每一秒你可以交换其中任意两个元素的位置。试在最少的时间内把这个排列变成是简洁的，并且给出最少的步数。

一些分析

图从何而来？

由于这是一个的排列，所以每个元素都会且只会出现一次，同理作为下标也只会出现一次；基于这点启发我们可以构造这样一个图：

这个图有编号依次为的n个节点，如果有那么我们就添加一条从到的有向边。

因为每个元素都会且只会出现一个，同理作为下标也只会出现一次，所以不难有每个点都只有一个入度和一个出度，也就是说这个这个图会由一系列简单的环组成。可以参考下面这个例子：

事已至此，我们不难发现：在图中代表的就是一个点到自己的自环； 对应的就是只有两个点彼此连接的环；所以我们的目标就变成了找到所有大于两个元素的环，然后把他们拆解为一系列两点环或者自环即可；

一次交换操作会对图产生什么影响？

我们还是按照上面的例子来做一个说明，如果我们对一个元素个数大于3的环做一次交换操作，那么我们可以做到从这个环里面拆出两点组成一个小环（这个小环）就对于情形2；最后面可能剩下1个或2个点都是能够满足条件的。

所以我们的策略已经呼之欲出力！找到所有元素个数为m大于2的环，把他交换次即可；我们算法层面需要实现的就是找到所有环即可，不做赘述，请看代码；

源代码可见:

#include <bits/stdc++.h>
using namespace	std;
#define MAX_LEN 1000005
 
int	main(void)
{
	int case_num, array_length, arr[MAX_LEN];
	cin >> case_num;
 
	for (int ii = 0; ii < case_num; ii++)
	{
		cin >> array_length;
		bool used[array_length];
		fill(used, used + array_length, false);
		int ans = 0;
		vector<int> loops;
		for (int jj = 0; jj < array_length; jj++)
		{
			cin >> arr[jj];
		}
 
		int turns = 0;
		int start;
		for (int kk = 0; kk < array_length; kk++)
		{
			turns = 0;
			if (used[kk])
			{
				continue ;
			}
			else
			{
				used[kk] = true;
				turns++;
				start = arr[kk] - 1;
 
				while (!used[start])
				{
					used[start] = true;
					turns++;
					start = arr[start] - 1;
				}
				loops.push_back(turns);
			}
		}
		for (int i : loops)
		{
			ans += (i - 1) / 2;
			// cout << "loops has " << i << " nodes\n";
		}
 
		cout << ans << endl;
	}
 
	return (0);
}

Accepted!!!

Dys的思路与想法

以下是我的一些思考与结果,需要用到的前置知识放在最后一部分----附录之抽代知识速成!,以及我会直接使用里面的定理与结论,另一方面放在最后也是为了能和思考题靠的更近(没想到吧,还有思考题😉).

问题的转换

其实可以发现,题干中就已经很直接的提及到要考虑到的排列了,那么在哪门学科里有关于排列的知识呢?知道的人已经知道了,那就是----抽代!启动!!!

我们先来考虑一下要满足什么条件才能是简洁的:

首先我们可以将视为对称群中的一个元素,若记,即对应以下置换:

那么!又是在干什么呢?

这不就是映射的复合吗?那它就是对应置换的乘法!所以说是简洁的,等价于置换!

简洁序列进一步的结构

上一步中我们已经将一个算法问题转换为一个抽象代数问题了.那么我们该进一步分析的结构了!

但是置换的乘法是很麻烦的,因为它甚至不一定是交换的.但是,我们可以把置换先拆成不相交轮换的乘积,那么就可以更轻松的处理了.而这些都是可以做到的!而我们就要用到附录里的定理1和定理2.

因此我们可以通过定理2把分解为不相交轮换的乘积,即:

其中各不相同!

那么再由定理1,也很容易得到:

注意:置换的乘积一般是不交换的!例如思考题2!

从而再根据思考题1可知,,当且仅当分解后的都是轮换!也就是都是2.

例如:

.

可以发现它分解后的都是轮换!那么可以下定论----这个是简洁的!实际上也确实如此.

.

分解后也是一个轮换,因此下定论----不是简洁的!

不简洁化为简洁的方法

那么将不简洁的序列化为简洁的思路也很明确了,那就是,将分解后的那些长度大于的轮换,用最少的步骤给它人为拆成若干个轮换.这里我们需要用到的方法就是附录里的定理3.

那么最优的办法应该就是二分法了吧,把长度的拆成两个的,然后再拆成四个的.

那么这里直接就上例子了.

例如:

.

很明显右侧是一个轮换.那我们交换和,也就是左乘上(这里置换的乘法我们取成从右往左)一个:

.

然后我们再分别交换和,和:

.

此时,我们便已经将化作是简洁的了!那对于该问题我们便已经完美的解决了!

解决!!!

总结

由于最近要开始看论文了,因此我出现在群里的频率都低了,出篇小题谢罪😭.但是有趣小题目前只有我出,其他讲师也开始忙碌起来,效率不是很高,我也要其他讲师狠狠出!!!

感谢我的同学给我提供的灵感以及他这部分的思考!不然我应该会鸽的更久一点(bushi).

如果你已经将我们两个人的思路都看完了的话,你会发现,原理其实都是一样的,但是却是从不同的角度去解决的.其实我个人觉得数学的魅力也就在这里,一道题的价值也就在于此.

以上的想法也是我个人独立想出来的,因此在一道非数学的题里,发现了熟悉的身影--抽象代数,即使第一眼从"1-n的排列"我就有所预兆,抽代可以启动了.但当我用抽代的想法,并且和xzr的另一种不同的想法不谋而合的时候,我还是感到很惊奇的.因此我建议你先自己想想,多思考,如果能有一点点自己的想法,都值得高兴与庆祝.因此这也是本文能够很快写出来的原因.(即使我自己的论文还拖着没看😣)

附录之抽代知识速成!

以下是韩士安的『近世代数』中置换群与对称群一节中的介绍,我直接拉了一些在上述过程中需要用到的知识在下面:

定义(对称群):

到的所有排列,构成了一个次对称群,记作.其每一个元素都称为一个置换.(由于对该问题的考虑并没有涉及到多少群的性质,因此暂时忽略掉对群的严格定义)

因此很容易知道的是,的元素个数为个.

例如:

.显然有个元素,也就是有个置换.

我们也可以将置换理解为一个映射,例如对于置换,我可以认为是分别将映为.

即.

事实上,在数学里面就是以映射的观点来考虑置换的,后面就能知道这样考虑的好处了,也就是:

置换的记法:

如果是中的一个置换,并且将分别映为,则可记:

其中第一行为原像,第二行则是对应的像.因此实际上由上下对应的元素所决定的.即还有:

于是我们便发现有以下这种特殊的置换,并且给它一个特殊的记号:

轮换:

如果将分别映为,而其余元素不变,则称为一个轮换,记为或者,即:

其中任意一个轮换都等于没有换,因此统一写成.

当然,数学里还将轮换称为对换,但是为了减少名词量,我在此处也还是称为轮换.通过思考题1后,我们可以发现用轮换的记号,可以使的对置换的讨论脱离出,也就是说,在一定程度上我们对是多少已经无关紧要了.

例如:

在中,轮换便等于.

在中,轮换便等于.

注意以上两者的不同!!!

将置换视为映射,而我们熟知的是映射可以做复合,也就是.那么对于置换而言,我们就有了广义的乘积,因此习惯性地从右往左乘,简称为乘积(为了构成群也必须要有乘法).

置换的乘法:

两个置换的乘积.

其本质是映射的复合,因此运算时要从右往左.并且置换的乘法一般是不交换的!(见思考题)

例如:

,

可知被映为,然后又被映为.因此总的来说,就被映为了.全部考虑完所有元素后,可知:

我们从思考题2知道,置换的乘法是不交换的,但是就像矩阵里边也有可以交换的情况一样,置换在满足一定条件后(例如思考题3和思考题4),那么就可以交换了.(虽然知道下面定理后这就是显然的,但是还是建议算一算,对乘法再熟悉一点)

不相交的轮换:

称与是两个不相交的轮换,如果满足:

也就是两个轮换中都没有共同的元素.

有了不相交的定义后,我们便得到以下两个很重要的定理:

定理1:

任何两个不相交轮换的乘积是可交换的.

定理2:

每一个中的置换都可以表示为一些不相交轮换的乘积.

例如:

在中,;.

而分解的方法也很简单,只要一直追着一个元素不放,直到它形成一个闭合的环为止.在上面第二个例子中,可以发现元素的痕迹:,因此便是.(在思考题5和思考题6中会有小练习的)

最后一个知识点则是,我如何将一个长的轮换拆成若干个短轮换呢,那以下定理就说明了拆成两个的情况了:

定理3:

我们只要交换特定两个位置的值就可以了!即:

当然上面定理的验证也还是比较直接的,直接将左侧的映射写出来便是:

然后注意力集中!(all you need is attention!)发现它就是右侧那一块.

有数学的地方,就能有思考题!

1. 验证一下:在中,,与此同时也有.

容易发现的是:只有是轮换的时候,.而当是轮换的时候,.

2. 验证:在中,.再计算从而验证置换的乘法是不可交换的.

3. 验证:在中,.

4. 验证:在中,.

5. 用不相交轮换的乘积写出和中的每一个元素.

6. 将写成不相交轮换的乘积.

抽代的参考资料

[1] 韩士安, 林磊. 近世代数, 第二版[M]. 北京: 科学出版社, 2009. P44-P55.

[2] Thomas W.Hungerford. Algebra[M]. Springer, 1974.