Schreier-Sims 算法的阐述

· · 算法·理论

在讲解该算法前，假定读者已经理解了 Burnside 引理 的前置定理
——拉格朗日定理 和 轨道-稳定子定理。

给定若干 n 元置换 p_1,p_2,\cdots,p_m\ (n\le 50)，如何判定由它们所生成的置换群

首先，根据 轨道-稳定子定理 $$|G_n|=|G(n)||G_n|$$ $n$ 的稳定子 $G_n=\{g\in G|g(n)=n\}$ 是 $G$ 的子群， 且 $G$ 中元素根据 $g(n)$ 的值被划分为 $G_n$ 的左陪集，即 $$g_1(n)=g_2(n)\Leftrightarrow g_1\circ G_n=g_2\circ G_n$$ 设 $G$ 中存在 $r\in G$ 使得 $r(n)=q(n)$，若 $q$ 在 $G$ 中，则 $$r\circ G_n=q\circ G_n$$ $$\exist g\in G_n,r\circ g=q$$ $$\exist g\in G_n,r^{-1}\circ q=g$$ $$r^{-1}\circ q\in G_n$$ 这样就将“$q$ 是否属于 $G$” 这一问题转化为了问题“$r^{-1}\circ q$ 是否属于 $G_n$”。 而 $G_n$ 可以视为 $n-1$ 元置换组成的置换群， 这样就将关于 $n$ 元置换的问题转化为关于 $n-1$ 元置换的子问题。 ------------------------------------------ 要实现上述的思路，我们需要实现以下两个步骤： 1. 在 $G_n$ 的所有左陪集里各取得一个代表元素 $r$。这样， 对于任意的 $q$ 总能找到相应的 $r$ 使得 $r(n)=q(n)$。 3. 给出 $G_n$ 的一组生成元，这样就将原问题转化为关于 $n-1$ 元置换的子问题。 步骤 1. 显然是可以用搜索实现的，其相当于确定 $n$ 的轨道 $G(n)=\{g(n)|g\in G\}$， 即 $n$ 能通过置换 $p_1,p_2,\cdots,p_m$ 变为哪些可能的值。 设求得的代表元构成集合 $R=\{r_1,r_2,\cdots,r_{|G(n)|}\}\quad(r_1=e)$， 其在计算群论中有一个专门的术语：**截面**，其定义为： > 对于群 $(G,*)$ 的子群 $H$，设 $H$ 的所有左陪集为 > $$r_1*H,r_2*H,\cdots,r_{[G:H]}*H\quad(r_1=e)$$ > 则称 $R=\{r_1,r_2,\cdots,r_{[G:H]}\}$ 为 $H$ 的 **左截面**。同理可定义 **右截面**。 > 下文所讲的陪集，截面若不加说明，统一为左陪集，左截面。 此外，对于群 $(G,*)$ 的子群 $H$，在求得 $H$ 的截面 $R$ 的基础上， 我们称 $g\in G$ 所在陪集的代表元素为 $g$ 的 **标准元素**，记为 $\operatorname{norm}(g)$，即 $$r\in R,r*H=g*H\Leftrightarrow\operatorname{norm}(g)=r$$ -------------------------------------------------- 接下来考虑如何实现步骤 2.，在已经求得了截面 $R$ 的基础上，我们有 > **（Schreier 引理）** 对于群 $(G,*)$ 和 $G$ 的生成元集合 $S$，若 $H$ 为 $G$ 的子群，其截面为 $R$，设 > $$S'=\{(\operatorname{norm}(s*r))^{-1}*s*r|r\in R,s\in S\}$$ > $\qquad\qquad\qquad\quad$ 则 $S'$ 为 $H$ 的生成元集合，即 $H=\left<S'\right>$。 > 证明：因为 $s*r$ 和 $\operatorname{norm}(s*r)$ 属于同一个陪集，显然有 $S'\subseteq H$，故 $\left<S'\right>\subseteq H$。 > $\qquad$ 接下来证明 $H\subseteq\left<S'\right>$。因为 $e\in R$ 且 $S$ 为 $G$ 的生成元集合， > $\qquad$ 故 $H$ 中任意元素 $h$ 总能表示成 > $$h=s_1*s_2*\cdots*s_k*r\quad(k\in\N,s_1,s_2,\cdots,s_k\in S,r\in R)$$ > $\qquad$ 的形式。若 $k=0$，显然 > $$h=r\in H\cap R=\{e\}\subseteq\left<S'\right>$$ > $\qquad$ 若 $k\not=0$，注意到 > $$h=s_1*s_2*\cdots*s_{k-1}*\operatorname{norm}(s_k*r)*(\operatorname{norm}(s_k*r))^{-1}*s_k*r$$ > $\qquad$ 于是设 > $$s_k'=(\operatorname{norm}(s_k*r))^{-1}*s_k*r,h'=h*(s'_k)^{-1}$$ > $\qquad$ 则 > $$\operatorname{norm}(s_k*r)\in R,s_k'\in S'\subseteq H$$ > $$(s_1*s_2*\cdots*s_{k-1}*\operatorname{norm}(s_k*r))=h'\in H$$ > $\qquad$ 即可归纳得到 $h'\in\left<S'\right>\Rightarrow h=h'*s_k'\in\left<S'\right>$。命题得证。 借助 Schreier 引理，即可用 $G$ 的生成元集合 $S$ 求得 $G_n$ 的生成元集合 $S'$。 由于 $G_n$ 的陪集数 $|G(n)|$ 最多为 $n$，求得的 $S'$ 大小最多为 $n|S|$。 ----------------------------------------------------- 直接使用 Schreier 引理，虽然能够求得 $G_n$ 的生成元集合 $S'$，但随着算法的一层层递归， $S'$ 的大小将达到 $\Omicron(n!)$ 级别，显然这是不可接受的。 考虑整个算法流程对 $G$ 结构的刻画。不难发现，整个算法像剥洋葱一般将 $G$ 分为了若干层 $$G\ge G_n\ge (G_n)_{n-1}\ge\cdots\ge (\cdots((G_n)_{n-1})\cdots)_1=\{e\}$$ 并给出了相邻层之间的截面。所有截面不仅一起构成了 $G$ 的一组 $\Omicron(n^2)$ 大小的生成元集合， 还描述了 $G$ 的结构，称为 $G$ 的 **强生成元**。 于是我们转而考虑增量维护 $G$ 的强生成元。每次尝试向 $G$ 中插入一个新生成元 $p$， 若 $p$ 不在 $G$ 中，首先用搜索扩充 $G_n$ 的截面，然后通过 Schreier 引理新增 $G_n$ 的生成元， 最后将新增的生成元尝试插入 $G_n$。 这样，我们就得到了通过一般生成元求解置换群强生成元的 **Schreier-Sims 算法**。 使用强生成元判定特定置换 $q$ 是否在 $G$ 中是 Schreier-Sims 算法的一部分。 对于一般的生成元集合 $S$，使用 Schreier-Sims 算法求出 $G$ 的强生成元后， 即可判定特定置换 $q$ 是否在 $G$ 中。 Schreier-Sims 算法的复杂度是多少呢？首先，每次尝试插入都要消耗 $\Omicron(n^2)$ 的时间用于判定。 其次，成功的插入最多有 $\Omicron(n^2)$ 次，总共通过 Schreier 引理新增 $\Omicron(n^3)$ 个生成元， 每个新生成元都会产生一次插入尝试。综上，Schreier-Sims 算法的时间复杂度为 $$\Omicron(|S|n^2+n^5)$$ Donald Knuth 已证明以上便是该算法的最坏时间复杂度。 ## 例题 > [**loj177 生成子群阶数**](https://loj.ac/p/177) > 给出 $m$ 个 $n$ 元置换，求这 $m$ 个置换生成的置换群的阶数。 > $\texttt{Data Range}:n,m\le 50

根据拉格朗日定理，求出强生成元后，置换群的阶数就是所有截面大小的乘积。
使用 Schreier-Sims 算法求出强生成元即可解决本题。

注意计算截面大小的乘积时需要高精度。

/*
this code is made by warzone
2024-09-08 23:47
*/
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
typedef unsigned int word;
struct READ{//快读快写
    char c,w;
    inline READ(){c=getchar();}
    template<typename type>
    inline READ& operator >>(type& num){
        while('0'>c||c>'9') c=getchar();
        for(num=0;'0'<=c&&c<='9';c=getchar())
            num=num*10+(c-'0');
        return *this;
    }
}cin;
const word W=1e7;
struct BigInt{//高精度类
    word num[16];
    inline void operator*=(const word x){
        for(word i=0,get=0;i<16;++i){
            get+=num[i]*x;
            num[i]=get%W,get/=W;
        }
    }
    inline void print()const{
        word i=15;
        while(i&&!num[i]) --i;
        printf("%u",num[i]);
        while(i--){
            putchar(num[i]/1000'000+'0');
            putchar((num[i]/100'000)%10+'0');
            putchar((num[i]/10'000)%10+'0');
            putchar((num[i]/1000)%10+'0');
            putchar((num[i]/100)%10+'0');
            putchar((num[i]/10)%10+'0');
            putchar(num[i]%10+'0');
        }
    }
}a;
word n,m;
struct perm{//置换类
    word num[64];
    inline perm(){}
    inline perm(const perm &p)=default;
    inline perm(const perm &p,const perm &q){//置换的复合
        for(word i=0;i<=n;++i)
            num[i]=p.num[q.num[i]];
    }
    inline perm _1()const{//逆置换
        perm p;
        for(word i=0;i<=n;++i)
            p.num[num[i]]=i;
        return p;
    }
}p;
std::vector<perm> section[64];//section[n] G_n 的截面
word norm[64][64];
//norm[n][m] 满足 g(n)=m 的 g 对应的标准元素（在 section[n]）中的编号
inline void insert(perm &p,const word n){
    // Schreier-Sims 算法主体，尝试插入元素 p（n 元置换）
    word m=n;
    for(;m>1&&norm[m][p.num[m]]!=0xffff'ffff;--m) if(p.num[m]!=m){
        p=perm(section[m][norm[m][p.num[m]]]._1(),p);
        if(p.num[m]!=m) break;
    }//检查 p 是否在群里
    if(m==1) return;//已经在群内
    const word siz=section[n].size();
    for(word i=0;i<siz;++i){
        word &get=norm[n][p.num[section[n][i].num[n]]];
        if(get==0xffff'ffff){
            get=section[n].size();
            section[n].push_back(perm(p,section[n][i]));
        }
    }//检查 G_n 的截面是否有扩充
    if(siz==section[n].size()){// G_n 的截面没有扩充的情况
        insert(p,n-1);
        for(word i=1;i<siz;++i){
            perm q(p,section[n][i]);
            q=perm(section[n][norm[n][q.num[n]]]._1(),q);
            //通过 Schreier 引理新增生成元
            insert(q,n-1);//尝试插入新生成元
        }
        return;
    }
    for(word i=siz;i<section[n].size();++i)
        for(word j=1;j<=n;++j)
            for(word k=1;k<section[j].size();++k){
                word &get=norm[n][section[j][k].num[section[n][i].num[n]]];
                if(get==0xffff'ffff){
                    get=section[n].size();
                    section[n].push_back(perm(section[j][k],section[n][i]));
                }
            }//使用搜索扩充 G_n 的截面
    std::vector<perm> add;
    for(word i=siz;i<section[n].size();++i){
        for(word j=1;j<=n;++j)
            for(word k=1;k<section[j].size();++k){
                const perm p(section[j][k],section[n][i]);
                add.push_back(perm(section[n][norm[n][p.num[n]]]._1(),p));
            }
        for(word j=0;j<siz;++j){
            const perm p(section[n][i],section[n][j]);
            add.push_back(perm(section[n][norm[n][p.num[n]]]._1(),p));
        }
    }//通过 Schreier 引理新增生成元
    for(auto &p:add) insert(p,n-1);//尝试插入新生成元
}
int main(){
    memset(norm,0xff,sizeof(norm));
    cin>>n>>m;
    for(word i=1;i<=n;++i) p.num[i]=i,norm[i][i]=0;
    for(word i=1;i<=n;++i)//初始时，每个截面只有恒等置换
        section[i].push_back(p);
    for(word i=1;i<=m;++i){//逐个尝试插入新生成元
        for(word j=1;j<=n;++j) cin>>p.num[j];
        insert(p,n);
    }
    a.num[0]=1;
    for(word i=1;i<=n;++i)//计算截面大小乘积
        a*=section[i].size();
    a.print();
    return 0;
}