置换群的计算机算法

第六章 置换群一. 概念题1.置换群以n 个数字{}1,2,...,n 间的所有置换操作为元素构成的群，称为n 阶置换群n S 。

2.置换群的类置换群中有相同轮换结构的元素互相共轭，他们的集合构成置换群的类。

3.置换群的产生子任两个数字的对换(),i j 可以写成()()()()111i j i j i =，因此n S 中任一置换都可以由()()()()12,13,14,,1n ⋅⋅⋅这些基本对换中的一些相乘得到，所以就称这()1n -个与符号'1'对换(){}1i 为n S 的产生子。

4.杨图任取一组配分数[]λ，12[][,,......]m λλλλ=，1210,m m j j n λλλλ=≥≥⋅⋅⋅≥>=∑，画n 格方格图，分成m 行，左边对齐，第一行含1λ格，第二行含2λ格，以此类推，这样的方格图称为杨图。

5.杨算符对于给定的杨表，所有横向置换之和称为它的横向算符P p =∑，所有纵向置换乘其置换宇称之和称为它的纵向算符qQ q δ=∑，杨算符等于横向算符和纵向算符的乘积，E PQ =。

6.杨盘与正则杨盘把自然数1到n 填入杨图，得到杨盘。

如在杨盘中，同一行中左面数小，同一列中上面数小，则称为正则杨盘。

7.什么是关联杨图？什么是关联表示？有些杨氏图，像[]4与41⎡⎤⎣⎦，[]3,1与22,1⎡⎤⎣⎦等，分别沿第一个方块的左上角到右下角的对角线转π角后可以互相重合，称之为关联杨图，这种图对应的不可约表示称为关联表示。

8.正则杨盘的大小自第一行开始自左至右比较两杨盘的填数，如果都相同，再比较第二行、第三行等，第一次发现填数不同时，填数大的正则杨盘大于填数小的正则杨盘。

9.置换n 个客体排列次序的变换称为置换。

10.轮换有一类特殊的群，如果在一个置换中，有（n-1）个客体保持不变，而余下的l 个客体顺序变换，即第1a 个位置的客体排列第2a 的位置，第2a 位置的客体排到第3a 位置，以此类推，最后第l a 位置的客体排到第1a 位置，形成一个循环。

群论是数学中研究群结构和性质的一个分支，而群作用和置换群是群论中的两个重要概念。

群作用是指群的元素在某个集合上的一种作用方式，而置换群则是指一种特殊的群作用，其中群的元素排列集合中的元素。

首先，让我们来探讨群作用。

群作用定义了群的元素是如何作用于某个集合上的。

具体来说，给定一个群G和一个集合S，如果对于群G的每个元素g和集合S的每个元素s，都存在一个新的元素gs满足群的封闭性（即乘法运算仍然属于群G），并且满足以下条件：对于群G的单位元素e，有es=s，以及对于群G的任意元素g1和g2，以及集合S的任意元素s，有(g1g2)s=g1(g2s)，那么我们称此为群G在集合S上的一个作用。

群作用的一个重要特点是同一元素的不同群作用结果不相同。

也就是说，对于群G的元素g和集合S的元素s1和s2，如果g(s1)=s2，则必然有g(s2)≠s1。

这反映了群作用的可逆性，即通过群的元素作用可以互相转换集合S中的元素。

接下来，我们来了解置换群。

置换群是一种特殊的群作用，其中群的元素是对一个集合进行排列的操作。

换句话说，置换群是由对集合中元素的排列所生成的群。

设集合S={1,2,...,n}，我们可以定义任意一个对集合S的排列为一个置换。

举个例子，对于集合S={1,2,3}，可以有置换（1,2,3），表示将元素1映射到2，元素2映射到3，元素3映射到1。

而置换群则是由所有这样的置换所生成的群。

置换群具有很多重要的性质。

首先，置换群是有限群，其元素的个数是n的阶乘n!。

其次，置换群是可逆的，每个置换都有一个逆置换。

此外，置换群的运算是可交换的和可结合的。

通过群论中的群作用和置换群的研究，我们可以探索很多有趣的数学问题。

例如，通过群作用，我们可以研究对称群和平凡群等抽象代数结构，从而深入探讨集合、函数和变换等数学概念之间的联系。

而通过置换群的研究，我们可以解决排列和组合等数学问题，为深入理解对称性和对称性破缺提供理论基础。

第五章 置换群与酉群§ n 阶置换群S n【概念】 （置换）将n 个数字{1，2，…，n}的排列n a a a 21映为排列n b b b 21，称为一个n 阶的置换，记为s , ⎪⎪⎭⎫⎝⎛=n n b a b b a a s 2121。

置换s 把a 1换为b 1，a 2换为b 2，…，a n 换为b n ，它决定于诸双数码的对换，与诸对数码的排列顺序无关。

【概念】 （置换群）概念两个置换r ，s 的乘积rs 为先实行置换s ，再实行置换r ，那么在此乘法下所有n 阶置换作成的集合，组成一个群，称为n 阶置换群或对称群，记为S n 。

单位元：恒等置换。

逆元：n S s ∈∀，⎪⎭⎫ ⎝⎛=n n b a b b a as 2121，⎪⎭⎫⎝⎛=-n n a b a a b b s 21211置换的乘法知足封锁性和结合律，S n 群的阶为n ！。

【概念】 （轮换）一种特殊形式的置换：⎪⎭⎫⎝⎛-113221e e e e e e e em m m 称为轮换，记为()m e e e 21，轮换数码的个数m 称为轮换的阶。

•系1 轮换内的数码作轮换，仍表示同一个轮换，即：()()()12113221-==m m m m e e e e e e e e e e e 。

•系2 两个轮换()m e e e 21和()n f f f 21假设没有公共数码，那么称它们彼此独立；彼此独立的轮换之间的乘积知足互换律，即：()()⎪⎭⎫⎝⎛=13221132212121f f f f f f e e e e e ef f f e e e n m n m()()m n e e e f f f 2121=•系3 任意的n 阶置换总能够分解为彼此独立轮换的乘积。

例如：=⎪⎭⎫ ⎝⎛316556432421（1 4 5）（2）（3 6）=（1 4 5）（3 6） ⎪⎭⎫ ⎝⎛=n n s 3321210=（1）（2）…（n ） 一阶的轮换将自身映为自身，可略去不记，故S 0=（1）=（2）=…=（n ）。

上海电力学院Shanghai University of Electric Power实验报告院系名称：计算机科学与技术学院 __ 课程名称： _____ _ 应用密码学 _ _ __ 实验项目名称：置换群相关的运算及实现 ________实验一置换群相关的运算及实现一、实验目的理解密码学相关基本概念理解并能够编写基本的古典密码体制熟练应用C++编程实现密码体制二、实验内容1、求S3的所有元素并输出所有的置换。

2、水域S3的任意两个置换元素，求他们的复合运算的结果。

3、给定S3的某个置换，求它的逆置换。

三、实验原理1.置换群：n元对称群的任意一个子群，都叫做一个n元置换群2.矩阵的复合运算3.矩阵的求逆运算四、实验步骤（包括流程图、功能模块）1.申请18个空间，将3个元素依次循环填入填充。

2.通过置换，求得所有置换群3.矩阵的复合运算4.矩阵的求逆运算【算法流程图】五、软件使用说明（开发环境、参数使用详细说明、实验结果+相应截图等）【功能模块】求取置换群for (int i = 0; i<3; i++){swap(Abelian[i * 6], Abelian[i * 6 + i]);swap(Abelian[i * 6 + 3], Abelian[i * 6 + 3 + i]);swap(Abelian[i * 6 + 4], Abelian[i * 6 + 4 + 1]);}矩阵的复合for (int i = 0; i<3; i++){for (int j = 0; j<3; j++)if (Abelian[3 * (m - 1) + i] == Abelian_Group_src[j])Compound_Operate[i] = Abelian[3 * (n - 1) + j];}逆矩阵for (int i = 0; i<3; i++){for (int j = 0; j<3; j++)if (Abelian[3 * (n - 1) + i] == Abelian_Group_src[j])inverse_operation[j] = Abelian_Group_src[i];}【开发环境】Visual Studio 2013 （Windows10）【参数使用】输入的三个元素：4、5、6选择做复合运算的两个置换：4、5求逆的矩阵编号：4【实验结果】六、参考资料（书籍或网络文章）《密码编码学与网络安全——原理与实践（第五版）》七、实验心得和总结八、源代码#include<iostream>#include<string.h>using namespace std;int main(){//1int *Abelian_Group_src = new int[3];cout << "请依次输入元素值：";for (int i = 0; i<3; i++)cin >> Abelian_Group_src[i];int Abelian[18];for (int i = 0; i<18; i = i + 3)//因为每个置换群的第一行都相同，所以只需要对剩下的一行操作即可。

在离散数学中，置换群和置换多项式是两个重要的概念。

它们在代数和组合数学中有广泛的应用，可以用来解决各种问题。

首先，我们来看看置换群。

置换群是由一组置换组成的集合，满足以下条件：先进行一个置换，然后再进行另一个置换，结果必须还是一个置换。

换句话说，如果我们用符号表示置换，那么对于任意两个置换a和b，它们的组合ab还是一个置换。

同时，存在一个特殊的置换，称为单位置换，它不改变任何元素的位置。

这样的一组置换及其运算构成了一个置换群。

置换群有许多重要的性质。

首先，置换群是封闭的，也就是说，任意两个置换进行组合的结果还是一个置换。

其次，每个置换都有一个逆置换，使得二者组合后等于单位置换。

此外，对置换的组合运算满足结合律，即(ab)c = a(bc)。

这些性质使得置换群成为一个具有代数结构的集合。

置换群在很多领域有着重要的应用。

在密码学中，置换群可以用来生成一组密钥，用于加密和解密信息。

在计算机图形学中，置换群可以用来进行图像变换，如旋转、缩放和平移等操作。

在组合优化中，置换群可以用来解决旅行商问题和分配问题等。

总之，置换群是许多数学和应用领域的基础概念。

接下来，我们来介绍置换多项式。

置换多项式是用来表示置换群元素的一种多项式。

对于一个置换，可以通过置换多项式的形式来表示它的元素移动情况。

例如，对于一个置换(1 2 3)，它将1映射到2，2映射到3，3映射到1。

我们可以通过置换多项式x^3 - 3x^2 + 2x来表示这个置换。

置换多项式有很多有趣的性质。

首先，置换多项式的次数等于置换的元素个数。

其次，置换多项式的系数可以用来表示元素的移动情况。

例如，在上面的例子中，系数-3表示元素2移动到了3的位置。

此外，置换多项式的乘积可以用来表示两个置换的组合。

置换多项式在代数和组合数学中有广泛的应用。

它们可以用来求解置换群的性质，如生成元和阶等。

同时，置换多项式还可以用来解决某些组合计数问题，如排列组合和组合逻辑等。

离散数学是数学的一个分支，研究离散的数学结构和离散的数学对象。

其中一个重要的概念就是群。

群是代数结构中的一种基本概念，它是一种由一组元素和满足一定性质的运算组成的数学对象。

在离散数学中，置换群是群的一种重要形式，而群同态则是群之间的一种特殊映射关系。

置换群是置换（permutation）的全体构成的群。

置换是一种将元素重新排列的操作，可以看作是对集合中元素的重新排序。

形式上，一个置换可以表示为一个列表或一个矩阵，其中每个元素被映射到另一个元素。

例如，对于集合 {1, 2, 3, 4}，一个置换可以是将元素1映射到元素3，元素2映射到元素2，元素3映射到元素1，元素4映射到元素4，表示为(1, 3, 2, 4)。

一个置换群是由所有可能的置换以及其组合所构成的群。

群运算可以定义为两个置换的复合运算，即将一个置换应用于另一个置换所得到的新置换。

在整数乘法下的正整数形成的群就是一个置换群的例子。

置换群的一个重要性质是它的元素可以分解为不相交循环的乘积。

不相交循环是置换的一种特殊形式，其中每个元素按照一个循环进行置换。

例如，对于置换(1, 3, 2, 4)，可以将其分解为两个不相交循环：(1, 3, 2)和(4)。

这种分解方式是唯一的，也就是说，对于任何一个置换，其分解形式是唯一的。

群同态是两个群之间的一种映射关系。

具体来说，设有两个群G和H，如果存在一个映射f：G → H，满足对于群G中的任意元素g1和g2，f(g1 · g2) =f(g1) · f(g2)，即映射保持群运算，那么称映射f是从群G到群H的一个群同态。

在置换群的研究中，群同态可以用于描述置换群之间的关系。

例如，对于两个置换群，可以定义一个映射f：G → H，将群G中的一个置换映射到群H中的一个置换。

如果映射f保持组合关系，即对于群G中的任意两个置换g1和g2，有f(g1 · g2) = f(g1) · f(g2)，那么这个映射就是一个群同态。

2.6 置 换 群上一节：任何n 阶群都与n S 的一个子群同构。

n S 的每一个子群都叫一个次置换群。

n S 中的每个元素都叫一个置换。

σ如果把1i 变成2i ，2i 变成3i ， ， 1k i -变成k i ，k i 变成1i ，其余元素保持不变，则称σ是一个k - 循环，记成()121k k i i i i σ-= 。

注意：()121k k i i i i σ-= 也可以写成()()231112k k k k i i i i i i i i σ--=== 。

例如(123)(231)(312)==。

当1k =时叫做1-循环，也就是恒等置换，记作(1)(2)()n ε==== 。

当2k =时叫做对换。

一般形式()12i i 。

无公共元素的循环称为不相交循环。

例如(135)与(24)不相交。

3S 的6个置换可以写成：1123(1)123ϕ⎛⎫== ⎪⎝⎭， 2123(23)132ϕ⎛⎫== ⎪⎝⎭，3123(12)213ϕ⎛⎫== ⎪⎝⎭， 4123(123)231ϕ⎛⎫== ⎪⎝⎭， 5123(132)312ϕ⎛⎫== ⎪⎝⎭，6123(13)321ϕ⎛⎫== ⎪⎝⎭， 于是{}3(1),(12),(13),(14),(123),(132)S =，注意这样写的好处是避免了对置换编号。

4S 的24个置换可以写成：(1)— 1-循环，1个；(12),(13),(14),(23),(24),(34)—2-循环，共6个；(123),(132),(124),(142),(134),(143),(234),(243)—3-循环，共8个； (1234),(1243),(1324),(1342),(1423),(1432)—4-循环，共6个；(12)(34),(13)(24),(14)(23)—2-循环乘2-循环，共3个。

合起来正好24个。

（1）不相交循环与不相交循环可以交换相乘；例如，12345(123)(45)(45)(123)23154⎛⎫== ⎪⎝⎭。