精华内容
下载资源
问答
  • 信息安全数学基础--群环域--置换群,对称群 博主是初学信息安全数学基础(整除+同余+原根+群环域),本意是想整理一些较难理解的定理、算法,加深记忆也方便日后查找;如果有错,欢迎指正。 置换群:设集合MMM是一...

    近世代数--置换群--置换permutation分解成什么?置换的级如何计算?

    博主是初学近世代数(群环域),本意是想整理一些较难理解的定理、算法,加深记忆也方便日后查找;如果有错,欢迎指正。
    我整理成一个系列:近世代数,方便检索。

    有一些概念。

    • 置换permutation:设集合 S S S是一个有限非空集合, G G G S S S到它自身上的所有元素一一映射,即 π : S → S \pi:S\rightarrow S π:SS
      在这里插入图片描述

    • 对称群symmetric group:当 S S S为具有 n n n个元素的有限集合 时,它的全部置换(所有一一映射,每个一一映射是所有元素的一一映射)所组成的群 G G G也称为 n n n次对称群,记为 S n S_n Sn

    例子: S = { 1 , 2 , 3 } S=\{1,2,3\} S={1,2,3}
    S n = S_n= Sn= { { 1 , 2 , 3 } { 1 , 2 , 3 } } , { { 1 , 2 , 3 } { 1 , 3 , 2 } } , { { 1 , 2 , 3 } { 2 , 1 , 3 } } , { { 1 , 2 , 3 } { 2 , 3 , 1 } } , { { 1 , 2 , 3 } { 3 , 1 , 2 } } , { { 1 , 2 , 3 } { 3 , 2 , 1 } } \left\{ \begin{aligned} \{1,2,3\}\\ \{1,2,3\} \end{aligned} \right\}, \left\{ \begin{aligned} \{1,2,3\}\\ \{1,3,2\} \end{aligned} \right\}, \left\{ \begin{aligned} \{1,2,3\}\\ \{2,1,3\} \end{aligned} \right\}, \left\{ \begin{aligned} \{1,2,3\}\\ \{2,3,1\} \end{aligned} \right\}, \left\{ \begin{aligned} \{1,2,3\}\\ \{3,1,2\} \end{aligned} \right\}, \left\{ \begin{aligned} \{1,2,3\}\\ \{3,2,1\} \end{aligned} \right\} {{1,2,3}{1,2,3}},{{1,2,3}{1,3,2}},{{1,2,3}{2,1,3}},{{1,2,3}{2,3,1}},{{1,2,3}{3,1,2}},{{1,2,3}{3,2,1}}

    简写: S n = { ( 1 ) , ( 2 , 3 ) , ( 1 , 2 ) , ( 1 , 2 , 3 ) , ( 1 , 3 , 2 ) , ( 1 , 3 ) } S_n=\{(1),(2,3),(1,2),(1,2,3),(1,3,2),(1,3)\} Sn={(1),(2,3),(1,2),(1,2,3),(1,3,2),(1,3)}

    • 置换群permutation group:置换群是对称群的子群。
    • 轮换cycle S S S是有限非空集合,如果我们从 S S S中任意元素 x x x开始重复置换,得到 π ( x ) , π ( π ( x ) ) , … … \pi(x),\pi(\pi(x)),…… π(x),π(π(x)),直到某个置换返回 x x x,那么我们称这些置换为一个轮换
      在这里插入图片描述
    • 对换transposition:只有两个元素的轮换。
    • 不相交的轮换disjoint cycle:两个轮换 σ = { i 1 , i 2 … … i r } , τ = { j 1 , j 2 … … j s } , \sigma=\{i_1,i_2……i_r\},\tau=\{j_1,j_2……j_s\}, σ={i1,i2ir}τ={j1,j2js}如果有 i k ≠ j l , k = 1 , 2 , … … r , l = 1 , 2 … … s i_k\neq j_l,k=1,2,……r,l=1,2……s ik=jl,k=1,2,r,l=1,2s,那么我们称这两个轮换 σ , τ \sigma,\tau σ,τ不相交。两个不相交轮换的乘积是可交换的commutative: σ ⋅ τ = τ ⋅ σ \sigma·\tau=\tau·\sigma στ=τσ

    例子: ( 1 , 3 , 4 ) , ( 2 , 5 ) (1,3,4),(2,5) (1,3,4)(2,5)。可交换的: ( 1 , 3 , 4 ) ⋅ ( 2 , 5 ) = ( 2 , 5 ) ⋅ ( 1 , 3 , 4 ) (1,3,4)·(2,5)=(2,5)·(1,3,4) (1,3,4)(2,5)=(2,5)(1,3,4)

    置换的分解

    任何置换都可以分解成不相交的轮换的乘积,而且分解成的轮换是唯一的。

    证明:数学归纳法
    假设集合 ∣ S ∣ = n |S|=n S=n

    • n = 1 n=1 n=1,则 τ = ( 1 ) \tau=(1) τ=(1)
    • 假设 n − 1 n-1 n1时结论成立;即 α n − 1 \alpha^{n-1} αn1可以写成 α 1 ⋅ α 2 … … ⋅ α r \alpha_1·\alpha_2……·\alpha_r α1α2αr的形式,其中 α i , ( i = 1 … … r ) \alpha_i,(i=1……r) αi,(i=1r)是一个轮换, α i 、 α j ( i ≠ j ) \alpha_i、\alpha_j(i\neq j) αiαj(i=j)不相交
    • 现在证明 S = { 1 , 2 , 3 … … , n } S=\{1,2,3……,n\} S={1,2,3,n}
      取一个置换: α n = \alpha^{n}= αn= { 1 i 1 } , { 2 i 2 } , … … , { n − 1 i n − 1 } , { n i n } \left\{ \begin{aligned} 1\\i_1 \end{aligned} \right\}, \left\{ \begin{aligned} 2\\i_2 \end{aligned} \right\}, ……, \left\{ \begin{aligned} n-1\\i_{n-1} \end{aligned} \right\}, \left\{ \begin{aligned} n\\i_n \end{aligned} \right\} {1i1},{2i2},,{n1in1},{nin}
      有两种情况:
      • i n = n i_n=n in=n,这种情况直接得出 α n = α n − 1 ⋅ ( n ) = α 1 ⋅ α 2 … … ⋅ α r ⋅ ( n ) \alpha^{n}=\alpha^{n-1}·(n)=\alpha_1·\alpha_2……·\alpha_r·(n) αn=αn1(n)=α1α2αr(n),是不相交的轮换的乘积形式;
      • i n ≠ n i_n\neq n in=n,则有 ∃ k ∈ { 1 , 2 … … n − 1 } , i k = n , α n = {\exists} k\in \{1,2……n-1\},i_k=n,\alpha^{n}= k{1,2n1}ik=nαn= { 1 i 1 } , { 2 i 2 } , … … , { k − 1 i k − 1 } , { k i k } , { k + 1 i k + 1 } , … … { n − 1 i n − 1 } , { n i n } \left\{ \begin{aligned} 1\\i_1 \end{aligned} \right\}, \left\{ \begin{aligned} 2\\i_2 \end{aligned} \right\}, ……, \left\{ \begin{aligned} k-1\\i_{k-1} \end{aligned} \right\}, \left\{ \begin{aligned} k\\i_{k} \end{aligned} \right\}, \left\{ \begin{aligned} k+1\\i_{k+1} \end{aligned} \right\}, …… \left\{ \begin{aligned} n-1\\i_{n-1} \end{aligned} \right\}, \left\{ \begin{aligned} n\\i_n \end{aligned} \right\} {1i1},{2i2},,{k1ik1},{kik},{k+1ik+1},{n1in1},{nin}
        • 这样 i k = n , i n ∈ { 1 , 2 … … n − 1 } , i_k=n,i_n\in \{1,2……n-1\}, ik=nin{1,2n1} α n = ( i k , i n ) α n − 1 ⋅ ( n ) \alpha^n=(i_k,i_n)\alpha^{n-1}·(n) αn=(ik,in)αn1(n),即**先把 i n i_n in换到前 n − 1 n-1 n1个对应关系中,然后就跟前一种可能是一样的。**展开来, α n = ( i k , i n ) ⋅ α 1 ⋅ α 2 … … ⋅ α r \alpha^n=(i_k,i_n)·\alpha_1·\alpha_2……·\alpha_r αn=(ik,in)α1α2αr
        • α 1 , α 2 … … , α r \alpha_1,\alpha_2……,\alpha_r α1,α2,αr中必定存在一个,且只存在一个(因为 α i , ( i = 1 … … r ) \alpha_i,(i=1……r) αi,(i=1r)彼此不相交) α i \alpha_i αi包含 i n i_n in,即 a i a_i ai ( i k , i n ) (i_k,i_n) (ik,in)相交
        • 假设是 α 1 \alpha_1 α1,可以写成 α 1 = ( i n , a , … … b ) \alpha_1=(i_n,a,……b) α1=(in,a,b),那么 ( i k , i n ) ⋅ α 1 = ( i k , i n , a , … … b ) , α n = ( i k , i n ) ⋅ α 1 ⋅ α 2 … … ⋅ α r = ( i k , i n , a , … … b ) ⋅ α 2 … … ⋅ α r (i_k,i_n)·\alpha_1=(i_k,i_n,a,……b), \alpha^n=(i_k,i_n)·\alpha_1·\alpha_2……·\alpha_r=(i_k,i_n,a,……b)·\alpha_2……·\alpha_r (ik,in)α1=(ik,in,a,b),αn=(ik,in)α1α2αr=(ik,in,a,b)α2αr,是互不相交的轮换,证毕。

    置换的级计算

    置换 σ \sigma σ

    • 本身是 r r r长轮换的话,那 o r d ( σ ) = r ord(\sigma)=r ord(σ)=r
    • 如果不是轮换,则置换可以分解为轮换, σ = σ 1 ⋅ σ 2 ⋅ … … ⋅ σ t \sigma=\sigma_1·\sigma_2·……·\sigma_t σ=σ1σ2σt,其中 σ i \sigma_i σi为轮换;那么 o r d ( σ ) = l . c . m ( o r d ( σ 1 ) , o r d ( σ 2 ) , … … o r d ( σ t ) ) ord(\sigma)=l.c.m(ord(\sigma_1),ord(\sigma_2),……ord(\sigma_t)) ord(σ)=l.c.m(ord(σ1),ord(σ2),ord(σt)), l . c . m ( ) l.c.m() l.c.m()是求最小公倍数。

    理解,为什么置换的级是分解轮换级的最小公倍数

    • 轮换的级 o r d ( σ i ) ord(\sigma_i) ord(σi)的意思是最少“转多少次”才能使数字不变;例子: ( 1 , 3 , 4 ) = (1,3,4)= (1,3,4)= { 1 3 } , { 3 4 } , { 4 1 } \left\{ \begin{aligned} 1\\3 \end{aligned} \right\}, \left\{ \begin{aligned} 3\\4 \end{aligned} \right\}, \left\{ \begin{aligned} 4\\1 \end{aligned} \right\} {13},{34},{41}
      “转1次”: ( 3 , 4 , 1 ) (3,4,1) (3,4,1)
      “转2次”: ( 4 , 1 , 3 ) (4,1,3) (4,1,3)
      “转3次”: ( 1 , 3 , 4 ) (1,3,4) (1,3,4)
      所以 o r d ( ( 1 , 3 , 4 ) ) = 3 ord((1,3,4))=3 ord((1,3,4))=3
      任意轮换的级就是这个轮换的元素个数
    • 置换的级:置换分解成了多个轮换,那么我们需要将这个置换转每个轮换级的最小公倍数次,才能使所有元素都不变。例子: ( 1 , 3 , 4 , 2 , 5 ) = ( 1 , 3 , 4 ) ( 2 , 5 ) , ( 1 , 3 , 4 ) (1,3,4,2,5)=(1,3,4)(2,5),(1,3,4) (1,3,4,2,5)=(1,3,4)(2,5),(1,3,4)需要转3次, ( 2 , 5 ) (2,5) (2,5)需要转2次,那么 ( 1 , 3 , 4 , 2 , 5 ) (1,3,4,2,5) (1,3,4,2,5)需要转6次。
    展开全文
  • 相关群的概念: 对称群(symmetric group),设X是一个集合(可以是无限集),X上的一个双射:a:X→X(即是置换)。集合X上的所有置换构成的族记为S(x),S(x)关于映射的...研究置换群的性质和构造的理论称为置换群论.

    相关群的概念:

    对称群(symmetric group),设X是一个集合(可以是无限集),X上的一个双射:a:X→X(即是置换)。集合X上的所有置换构成的族记为S(x),S(x)关于映射的复合运算构成了一个群,当X是有限集时,设X中的元素个数为n,则称群S(x)为n次对称群。
    将S(x)的子群统称为变换群(transformation group)。
    置换群

    一类具体的有限群。有限集合到自身的一一映射称为一个置换。由全排列知识可知,这样的置换共有 n ! n! n!个。
    研究置换群的性质和构造的理论称为置换群论.凯莱(Cayley,A.)证明:任何一个有限群都同构于一个置换群.因此,可以把一切有限群都看成置换群.由于置换群比抽象群更为直观,而一些数学对象的自同构群是以置换群的面貌出现的,所以,在历史上对置换群的研究先于对抽象群的研究.著名的伽罗瓦理论就是把高次方程的根式可解性的研究转化成为对置换群的研究的,事实上,伽罗瓦(Galois,E.)本人就曾得到有关置换群的一些深刻定理。

    特殊的置换:轮换
    两个元素的轮换:对换
    置换与轮换的性质

    (1)如果 [公式] 和 [公式] 是 [公式] 中的两个不相交的轮换,则 [公式]
    (2)除恒等置换外, [公式] 中的任何一个置换都可以(不计顺序的意义下)唯一地分解为不相交的轮换的乘积。
    (3)任何一个轮换都可以分解为若干个对换的乘积。从而任何一个置换都可以分解为若干个对换的乘积。
    (4)任一给定的置换分解为对换的乘积时,无论何种分解方式,得到的对换个数奇偶性不变。

    交错群

    如果一个置换等于偶数个对换的乘积,则称之为偶置换;否则称为奇置换。所有偶置换构成的集合,按照置换的复合运算构成一个群,称为n次交错群(alternating group),记作 An,则有|An|=n!/2 。

    以{1,2,3}为例,集合 [公式] 中的置换有6种情况,读者可以自行列出这6种置换。易知,这6种置换都是轮换,因此可以得到S3={(1),(1,2),(1,3),(2,3),(1,2,3),(1,3,2)}。请注意,(1,2,3) 和 (2,3,1) 还有 (3,1,2) 表示的是同一个置换。
    (1,3,2)=(1 2 3;3 1 2)

    3次对称群S3是非交换群。事实上,S3是最小的非交换群。

    数字华容道

    任一给定的置换分解为对换的乘积时,无论何种分解方式,得到的对换个数奇偶性不变。

    视频描述链接

    数字华容道的通解
    15数码问题与A*算法
    https://github.com/AChep/15puzzle/releases或至谷歌应用商店下载

    表排序(现实世界物体的排序)

    先编好顺序,
    在这里插入图片描述
    置换
    每个环(轮换)只需置换一次

    展开全文
  • 置换群的整幂运算【置换群

    千次阅读 2015-08-03 21:28:09
    置换群的整幂运算 定理及结论: 1.在置换群中有一个定理:设 T^k = e (T 为一置换,e为单位置换(单位置换:映射函数为 f(x) = x 的置换)),那么k的最小正整数解是 T 的拆分的所有循节长度的最小公倍数. 2.设 T^k =...
    置换群的整幂运算
    定理及结论:

    1.在置换群中有一个定理:T^k = e(T 为一置换,e为单位置换(单位置换:映射函数为 f(x) = x 的置换)),那么k的最小正整数解是 T 的拆分的所有循节长度的最小公倍数.

    2.设 T^k = eT 为一循环,e为单位置换),那么k的最小正整数解为 T 的长度.

    3.单位置换就是若干个只含单个元素的循环的并,也就是说,长度为 L 的循环, L 次的幂(T ^ L),把所有元素都完全分裂了.

    推论过程:
    假设 T = (2,3,1,5,6,4),则长度 n = 6, T^6 = (T^2)^3;
    先将 T 进行映射,(2 -> 3, 3 -> 1, 1 -> 5, 5 -> 6, 6 -> 4, 4  -> 2)得到 T',然后将 T'进行排序得到 T.



    可以看出 T^2 刚好将 T 分成循环节长度为3的两份,并且每一个循环节所包含的的数都是 T 的奇数项上的数或者偶数项上的数!


    可以看出 T^3 刚好将 T 分成循环节长度为2的三份,并且每一个循环节所包含的的数都是T中项数 mod 3  = (0,1,2)项上的数!


    与前面有所不同的是 T^4 并没有按预期将 T 分成4份,只分成循环节长度为3的两份,并且每一个循环节所包含的的数都是 T 的奇数项上的数或者偶数项上的数!


    可以看出 T^5 并没有将 T 分裂成5份,仅仅只是改变了 T 的顺序!

    根据置换群中的定理1可知循环的分裂程度与 gcd(k,l) 有关!(l为循环长度,k为多少次幂)
    从上述推论过程可以得出 gcd(6,6) = 6,因此可以将循环分成6份,gcd(2,6) = 2,gcd(3,6) = 3,gcd(4,6) = 2,gcd(5,6) = 1也一一与推论中的结果对应!

    结论:
    1.一个长度为L的循环T,如果L是k的倍数,则T^k是k个循环的乘积,每个循环中所包含的元素分别是T中下标i mod k = 0,1,2...的数.
    2.一个长度为L的循环T,如果 gcd(k,l) = 1,T^k循环不一定与T相同;
    3.一个长度为L的循环T,T^k是 gcd(k,l) 个循环的乘积,每个循环中所包含的元素分别是T中下标i mod gcd(k,l) = 0,1,2...的数.

    ps:大量参考和引用 潘震皓《置换群快速幂运算 研究与探讨》的国家集训队论文,具体实例及证明请参考原文!
    展开全文
  • 置换群

    千次阅读 2015-09-16 18:01:54
    置换群 看了几天置换群,一直没搞清楚定义是怎么回事,一个置换可以写成若干循环的乘积,那么如果置换求幂的话,一个循环不会跑到另一个循环里面去。 我们可以简单理解为这几个位置的数来回换。 poj3270 给出一列...

    置换群

    看了几天置换群,一直没搞清楚定义是怎么回事,一个置换可以写成若干循环的乘积,那么如果置换求幂的话,一个循环不会跑到另一个循环里面去。

    我们可以简单理解为这几个位置的数来回换。

    poj3270

    给出一列数,求将这列数排成升序的最小花费,这里花费定义为交换两个数的和。
    例如给出一排数8 4 5 3 2 7,那么我们最终的状态为2 3 4 5 7 8,这里的轮换有(8 2 7)(4 5 3),这里8应该在第六个位置,
    而第6个位置是7,7应该在5这个位置,而第5个位置为2,2应该在1这个位置,这样就到了8所在的位置,我们称这是一个轮换。
    首先需要明确的一点是对于每个群,假设有k个数,那么我们需要交换k-1次得到升序。
    对于每一个群,我们有两种换发:
    1.群里换,拿群里最小的数t与其他每个数交换,共k-1次,花费为:sum+(k-2)*t.
    2.将这个数列最小的数m,拉入这个群,与该群最小的数t交换,然后用这个最小的数与其他数交换k-1次,然后再将m与t换回来,这样
    花费为:sum+t+(k+1)m
    那么最小花费我们取两者中最小的,即sum+min{(k-2)*t,t+(k+1)*m}.
    对于这个题关键就是怎么确定每个群,我们利用计数排序,得到每个数应该在的位置,然后循环判断这个位置是否已经被访问了。时间
    复杂度为O(n)

    代码:

    #include<map>
    #include<string>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<iostream>
    #include<algorithm>
    #include<bitset>
    #include<climits>
    #include<list>
    #include<iomanip>
    #include<stack>
    #include<set>
    using namespace std;
    int sum,num;
    int a[10010],rank[100010];
    bool vis[100010];
    set<int>st;
    void dfs(int val)
    {
    	vis[val]=1;
    	sum+=val;
    	num++;
    	st.erase(val);
    	if(!vis[a[rank[val]]])
    		dfs(a[rank[val]]);
    }
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	int amn=INT_MAX;
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",a+i);
    		amn=min(amn,a[i]);
    		rank[a[i]]++;
    		st.insert(a[i]);
    	}
    	for(int i=1;i<=100000;i++)
    		rank[i]+=rank[i-1];
    	int ans=0;
    	while(st.size())
    	{
    		sum=num=0;
    		int t=*st.begin();
    		dfs(t);
    		ans+=min(sum+(num-2)*t,(amn+t)*2+sum-t+amn+(num-2)*amn);
    	}
    	printf("%d\n",ans);
    	return 0;
    }


    poj2369

    给出1-n的一个排列,a1,a2,...,an,表示P(1)=a1,P(2)=a2,...,P(n)=an,P(P(1))=P(a1),P(P(2))=P(a2),
    ...,P(P(n))=P(an).问经过多少次后使得P(1)=1,...,P(n)=n.
    这个是置换群的概念题,找到每个循环节,确定其长度len1,len2,...,lenk,求他们的最小公倍数。
    对于题目中给定的一个例子进行分析:
    1 2 3 4 5
    4 1 5 2 3
    上面定义了函数P,那么我们可以看出这个置换可以写成(1 4 2)(3 5),这样循环1中的数绝对不会跑到第二个循环中,每个循环i需要经过leni次后就可以到达目的状态,所以我们只需要确定各个循环节长度的最小公倍数。

    #include<map>
    #include<string>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<iostream>
    #include<algorithm>
    #include<bitset>
    #include<climits>
    #include<list>
    #include<iomanip>
    #include<stack>
    #include<set>
    using namespace std;
    int gcd(int a,int b)
    {
    	return b==0?a:gcd(b,a%b);
    }
    int lcm(int a,int b)
    {
    	int t=gcd(a,b);
    	return a/t*b;
    }
    int a[1010],vis[1010];
    void dfs(int val,int step)
    {
    	vis[val]=step;
    	if(!vis[a[val]])
    		dfs(a[val],step+1);
    }
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    		scanf("%d",a+i);
    	int ans=1;
    	for(int i=1;i<=n;i++)
    	{
    		if(!vis[a[i]])
    		{
    			dfs(a[i],1);
    			ans=lcm(ans,vis[i]);	
    		}
    	}
    	printf("%d\n",ans);
    }


    poj1026
    首先给出一个置换,然后给出一个字符串,问置换k次之后得到的字符串是什么?
    我们求出来子循环,然后对每个子循环计算k次之后置换群变成什么排列,用b[0],b[1],...,b[t-1]表示一个子群,那么长度为t,经过一次置换后变成b[0]=b[1],b[1]=b[2],..,b[t-1]=b[0],所以经过k次后变成
    b[(0+k)%t],b[(1+k)%t],..,b[(t-1+k)%t],即b[i]->b[(i+k)%t].
    代码:

    #include<map>
    #include<string>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<iostream>
    #include<algorithm>
    #include<bitset>
    #include<climits>
    #include<list>
    #include<iomanip>
    #include<stack>
    #include<set>
    using namespace std;
    int hehe;
    int a[210],num[210],ans[210];
    bool vis[210];
    int dfs(int pos,int step)
    {
    	num[step]=pos;
    	vis[pos]=1;
    	int t;
    	if(!vis[a[pos]])
    		t=dfs(a[pos],step+1);
    	else
    		t=step;
    	ans[pos]=num[(step-1+hehe%t)%t+1];
    	return t;
    }
    char s[210],ss[210];
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF)
    	{
    		if(n==0)
    			return 0;
    		for(int i=1;i<=n;i++)
    			scanf("%d",a+i);
    		while(1)
    		{
    			scanf("%d%*c",&hehe);
    			if(hehe==0)
    				break;
    			gets(s);
    			memset(vis,0,sizeof(vis));
    			for(int i=1;i<=n;i++)
    				if(!vis[i])
    					dfs(i,1);
    			int len=strlen(s);
    			for(int i=1;i<=n;i++)
    				ss[ans[i]-1]=i>len?' ':s[i-1];
    			ss[n]='\0';
    			for(int i=n-1;i>-1&&ss[i]==' ';i--)
    				ss[i]='\0';
    			puts(ss);
    		}
    		puts("");
    	}
    }

     poj1721
    洗牌机
    给出洗牌规则,如果位置I上的牌是J,而且位置J上的牌是K,那么通过洗牌机后位置I上的牌将是K。
    首先给出初始顺序a1,a2,...,an,在位置ai处放置ai+1,得到初始序列为x1,x2,...,xn,经过s次洗牌之后,得到新的序列p1,p2,...,pn,现在给出最终序列即s,让我们求xi。这个完全可以用模拟来做,但是时间复杂度可能会高,我们可以求出循环节t,那么s=s%t之后,我们在进行洗n-s次就可以了。

    #include <iostream>
    using  namespace  std;
    const  int  N=1001;
    int  a[N],b[N],m[N];
    int  main()
    {
         int  i,n,s,j,t;
         cin>>n>>s;
         for (i=1;i<=n;++i)
         {
             scanf ( "%d" ,&a[i]);
             m[i]=a[i];
         }
    //  memset(used,0,sizeof(used));
         //找到循环节
         t=0;
         bool  flag;
         while (1)
         {
             for (i=1;i<=n;++i)
                 b[i]=a[a[i]];
             ++t;
             flag= true ;
             for (i=1;i<=n;++i)
             {
                 if (b[i]!=m[i])
                 {
                     flag= false ;
                     break ;
                 }
             }
             if (flag)
                 break ;
             for (i=1;i<=n;++i)
                 a[i]=b[i];
         }
         s=s%t;
         t=t-s;
         for (i=1;i<=n;++i)
                 a[i]=b[i];
         while (t--)
         {
             for (i=1;i<=n;++i)
                 b[i]=a[a[i]];
             for (i=1;i<=n;++i)
                 a[i]=b[i];
         }
         for (j=1;j<=n;++j)
             printf ( "%d\n" ,b[j]);
         return  0;
    }

     

    展开全文
  • 离散数学 06.03 置换群

    千次阅读 2018-01-20 19:07:53
    置换群
  • 几道置换群题目

    2020-10-10 13:25:41
    最近学了置换群,然后就想着写几道 POJ - 1026 Cipher VJ 题意: 题目意思是给一个置换,然后给一些字符串和一个整数k,要求对这些字符串进行k次置换 思路: 非常基础的题,要求置换k次,那么就把置换中的每一个环向...
  • 纽结群到置换群的表示,杨志青,高玉豹,本文是从群的角度对纽结进行研究,构造出了一种从纽结群到置换群的表示,可以更好的反映纽结的性质。通过把这种方法的推广,计算
  • 离散数学应该学过置换群的相关概念,置换本质就是映射,可以理解成一个正方形绕其中心逆时针旋转90度,就可以看作是正方形四个顶点的置换。 置换会形成一个环。且如果一个状态经过置换后跟原来相同,可以认为该状态...
  • 置换群题目汇总

    千次阅读 2015-04-21 16:28:29
    首先介绍一下什么是置换群,不说一些繁琐的概念。 首先给你一个序列,假如: s = {1 2 3 4 5 6} 然后给你一个变换规则 t = {6 3 4 2 1 5} 就是每一次按照t规则变换下去 比如这样 第一次:6 3 4 2 1 5 第二次...
  • 近世代数--置换群--一个置换的例子

    千次阅读 2020-12-11 23:48:40
    近世代数--置换群--一个置换的例子 博主是初学近世代数(群环域),本意是想整理一些较难理解的定理、算法,加深记忆也方便日后查找;如果有错,欢迎指正。 在S4S_4S4​中,令K={(1),(12)(34),(13)(24)}K=\{(1),(12)...
  • 群论与置换群入门

    千次阅读 2019-08-18 06:56:27
    是一个二元组G=(S,f)G=(S,f)G=(S,f),其中SSS是一个集合,fff是一个二元运算,满足: 封闭性:x,y∈S⇒f(x,y)∈S,x,y\in S\Rightarrow f(x,y)\in S,x,y∈S⇒f(x,y)∈S,. 结合律:x,y,z∈S,f(x,f(y,z))=f(f(x,y...
  • 笔者在研究置换群计算问题中,使用C语言设计了若干实用的关于置换运算的小程序,写出来供大家参考。这些程序的设计基础是将置换简记为,称之为置换的简约式.用此进行置换的运算非常方便,例如:用字符数组a、b、c...
  • 给出26个大写字母的置换B,问是否存在一个置换A,使得A^2=B   题解: LRJ大白书上的例题,需要推一下规律。 规律:两个长度为n的相同循环相乘,当n为奇数时结果也是一个长度为n的循环;当n为偶数时分裂...
  • 抽象代数的代码实现(1) 置换群

    千次阅读 2019-04-16 21:49:18
    之前做了一个四国军棋软件,做到最后我发现工作量已经爆炸了,我需要去寻找一个全新的算法,所谓深度学习的算法也许有效果但是对于没有计算资源的人来说并不适用。 我其实是挺喜欢数学的,我总觉得数学上的一些思想...
  • 计算N个递增有序元素1~N,多少次置换群的运算能够还原成1~N。 解题思路: 据说……置换群中有一个定理:设T为一置换,e为单位置换,T^k=e,那么k的最小正整数解是T的拆分的所有循环长度的最小公倍数。 ...
  • 置换群小结

    千次阅读 2016-01-27 15:22:07
    置换在ACM里貌似经常碰到,以前不会,一直瞎搞,做不出,最近学了下,感觉懂了点东西,但是还是很多不会做
  • 置换群,顾名思义,就是置换组成的群,这个置换就是双射变换的意思,因此大家都是对称群的子群。大家老换来换去的也不分谁是谁了,干脆就1234表示吧。K-循环就是大家像跑火车一样跑一圈。 无公共数码的意思是两个...
  • 置换 置换群 应用 http://hi.baidu.com/foreverlin1204/item/5bafa5e7e95629acc10d758b http://blog.163.com/myq_952/blog/static/863906320110211731329/ 置换的概念是什么?一个有限集合的一一变换叫做置换...
  • HDU-置换群

    2015-01-27 22:21:25
    问题及代码: ...*All rights reserved....*问题描述:As a unicorn, the ability of using magic is the distinguishing feature among other kind of pony....置换群。 学习心得: 就是按规律置换。
  • [学习笔记]置换群

    2019-01-04 08:22:00
    置换群是群论的一种:必须要知道的: 置换群和Burnside引理,Polya定理 理解一下 这里置换就是旋转同构的表示,方案就是“染色方案” m种置换,假如所有可能的方案,每种同构的方案都算了m次。(每种置换都有...
  • 置换群2

    2017-11-17 15:30:00
    接着上一节,为了研究置换群的结构,我们来考虑对称群$S_n$和交错群$A_n$的的生成元系. 定理1 对称群$S_n$可以由$(12),(13),\cdots,(1n)$生成,即$S_n=<(12),(13),\cdots,(1n)>$. 证明 首先$<(12),\cdots,...
  • 置换群幂运算

    千次阅读 2013-09-24 10:40:22
    1.置换群中有一个定理:设T为一置换,e为单位置换,T^k=e,那么k的最小正整数解是T的拆分的所有循环长度的最小公倍数。 此定理用来解决Poj 2369Permutation 2.T^k将长度为L的置换T分裂成gcd(L,K)份,每个循环...
  • Polya计数定理 组合数学是大三的课程,相关知识点很多还没有学到,但是它似乎很有用,寒假自己先看一看,有错误欢迎指正。 1.群的定义: 给定一个集合G={a,b,c,……}和集合G上的...置换群是最重要的有限群,所有的
  • 群论——置换群

    2018-03-14 15:04:00
    最近研究了一下有关置换群的东西……群论这个东西博大精深,我也就大概知道一下群的概念(网上随处可见)……置换这个东西博大精深,我也就大概该了解了一下相关概念:·置换:我们所说的置换是指集合论中的置换,并不是...
  • ACM_置换群 burnside引理 Polya定理

    千次阅读 2016-06-27 14:06:01
    置换群也是群论当中一个比较重要的内容,可是在离散课上老师直接跳过了这章内容我也是……(日了dog了),自己看了半天资料总算是有点眉目了。 1.置换群:…… 2.burnside引理:…… 3.Pólya定理:……
  • Codeforces 441D 题意:定义理想序列a[]:对于任意的i有a[i] = i。给出一个1到n的排列p[],可以将...tags:才知道置换群,看题解码的。。 使得一个排列有序的最小交换次数 = n - 置换群数目。 置换群,A->B,B...
  • 置换群 学习笔记

    2021-05-24 09:59:19
    置换群 学习笔记 参考博客: https://www.cnblogs.com/maoyiting/p/14171300.html#/cnblog/works/article/14171300 详细定义 & 证明可以看上面的博客,这里主要给出两个定理及其应用。 Burnside 引理 表述: ...
  • Cipher POJ - 1026(置换群)

    2020-07-17 19:21:41
    k可能会很大,不能暴力,所以要用置换群,找出轮换的环,假设环中有m个数,那么每编码m次,就代表这又回到了初始状态,可以用k%m,这样减少编码的次数。如果在记录轮换的位置,那么对于轮换中的第i个字符编码k次,就...
  • POJ 3270 置换群

    2016-04-29 19:14:22
    第二种是在一个置换群里引入这整序列的最小数(不在此置换群里),然后这个置换权就和有最小数的那个置换群合并了。再用第一种方法计算开销。此方法增加了引入最小的开销但是减少了单纯群内交换的开销,所以有可能比...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,599
精华内容 2,239
关键字:

置换群的计算