引言

本篇将记录我对一道算法题的一些思考,而这题的思路应该比较明显一些.因为它直接就说了,是对的一个排列,那么对称群应约而至.并且利用一些关于置换的性质,其实便能够很好地解决这个问题,毕竟抽代本身就是为了抽离出一个便于操作与计算的代数结构,直接抓住重点.

在此之前,我对于抽代也只是学习群环域这些理论知识,虽然知道计算机系也要学抽代,用抽代,但一直没有直观的感受.而对这个问题的思考过程中,之前学过的抽代知识自动地蹦出来并且很快地解决了问题,并没有用到多少复杂的内容.虽然对于抽代知识的考察并没有多少,但是在一个非数学的题目下,发现熟悉的身影,肯定还是觉得惊奇的,即使冥冥之中已经有所暗示.

因此我认为这还是很好的一个题,可以去启发其他同学的思考,不管是非数学系的还是数学系的.因此我打算写一篇比较详细的文章,所以写的内容里一半是抽代的一些概念,一半是解释概念时用的例子,解决算法问题的部分并没有多少.因此那一篇我就不会再搬过来了,在此处直接贴一个图片即可.

问题

题目来源可见原题链接,下面给出题目图片:

然后就是!『著名算法大师』Paitsai对该问题的简单翻译:

定义一个的排列(我图中用表示)是简洁的(我图中则是称为美好的),当且仅当均满足:或者.

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

想法

以下是我对该问题的思考:

纠错!!!(2024.11.08)

事实3其实不对,事实上是是轮换的话,那么,根据群元素的阶就很容易理解了.这下功夫不到家了,还好在写给其他人看的时候发现了.😥😥😥