如果有一个群 G 的强生成集,因为已经得到了所有 G^{(i)} 稳定器的生成器,那么很容易得到 G 的阶。部分基(partial base)B = [b_{1},\cdots, b_{k}] 和部分强生成集 S 是集合 B \in \Omega 和集合 S \subseteq G,使得 S 的任何元素都不能固定 B 的每个元素。
非空部分基 B = (b_{1},\cdots, b_{k}]。部分强生成集 S。集 C:= [b_{2},\cdots,b_{k}],T := S \cap G_{b1},并递归地应用于输入 C, T,以将它们修改为 H = \langle T \rangle 的基和强生成集。
设 B := B \cup C,S := S \cap T。用筛选算法在 H \leqslant G_{b_{1}} 中进行成员资格测试(Membership testing,检查集合(列表、集合、字典等)是否包含特定元素)。对 G_{b_{1}} 测试每个 Schreier 生成器 s 以查看 s \in H。如果都在 H 中,那么有 H = G_{b_{1}}, 返回 B,S,。否则到步骤 4。
否则有一个 Schreier 生成器 s \in G_{b_{1}} 但 s \notin H。设 S := S \cup {s}。如果 s 固定了 B 的所有点,将一个由 s 移动的 \Omega 点附加到 B。回到步骤 2。
#include<iostream>usingnamespacestd;constintmaxn=50;// Maximum size of omega = {1, ,n}constintmaxr=10000;// Maximum number of generatorsclassPermutation{// interface for permutationspublic:intp[maxn];// the images of the points 0.. maxn-1Permutation(){n=maxn;};// constructorsPermutation(intm){n=m;};Permutation(intm,charc){n=m;switch(c){case'i':for(inti=0;i<n;i++)p[i]=i;break;// identitydefault:for(inti=0;i<n;i++)p[i]=-1;break;// undefined}}Permutationoperator*(Permutationparam)const{// multiplicationPermutationresult(n);for(inti=0;i<n;i++)result.p[i]=param.p[p[i]];return(result);}voidoperator*=(Permutationparam){// direct multiplicationfor(inti=0;i<n;i++)p[i]=param.p[p[i]];}Permutationinverse()const{// inversePermutationresult(n);for(inti=0;i<n;i++)result.p[p[i]]=i;return(result);}boolisdefined()const{return(p[0]>-1);}// if it is definedboolisidentity()const{// if it is the identityfor(inti=0;i<n;i++)if(p[i]!=i)returnfalse;returntrue;}booloperator==(Permutationparam)const{// comparisonfor(inti=0;i<n;i++)if(param.p[i]!=p[i])returnfalse;returntrue;}voidinput(){for(inti=0;i<n;i++){cin>>p[i];p[i]--;}}// inputvoidoutput()const{for(inti=0;i<n;i++)cout<<p[i]+1<<" ";cout<<endl;}// outputvoidsetn(intm){n=m;}private:intn;// size of omega = {1, ,n}};intn;// size of omega = {1, ,n}intr;// number of generatorsPermutation*g=newPermutation[maxr];// the generatorsintnr;Permutation*newg=newPermutation[maxr];intcosreps;// number of (= size of orbit of alpha)Permutation*cosrep=newPermutation[maxn];// coset representatives (to store the output of// SchreierTree)Permutationundefined(maxn,'u');/****** ScheierTree ******/voidScheierTree(intalpha){// depth first search to determine the orbit of alphastaticPermutationgen(n,'i');// group element moving original alpha to actual alphastaticintag;// image of actual alpha under generator g[j]cosrep[alpha]=gen;cosreps++;for(intj=0;j<r;j++){ag=g[j].p[alpha];if(!cosrep[ag].isdefined()){gen*=g[j];ScheierTree(ag);gen*=g[j].inverse();}}}voidSchreierSims(){intalpha=0;Permutationsg;cout<<"THE ORDER OF THE GROUP:\n";do{cosreps=0;for(inti=0;i<n;i++)cosrep[i]=undefined;// get the coset representatives for G(alpha)ScheierTree(alpha);// schreier lemma loop to get the schreier generatorsnr=0;for(inti=0;i<n;i++){if(cosrep[i].isdefined())for(intj=0;j<r;j++){// calculate the (schreier) generatorssg=cosrep[i]*g[j]*cosrep[g[j].p[i]].inverse();boolalreadyhavethis=sg.isidentity();for(intk=0;k<nr;k++)if(sg==newg[k])alreadyhavethis=true;if(!alreadyhavethis)newg[nr++]=sg;}}cout<<cosreps<<flush;if(cosreps>1)cout<<"*";r=0;for(intj=0;j<nr;j++){g[r++]=newg[j];}alpha++;}while(cosreps>1);cout<<endl;}intmain(){cout<<"n ( Size of Omega = {1..n} ) ? ";cin>>n;for(intj=0;j<n;j++){g[j].setn(n);newg[j].setn(n);}undefined.setn(n);cout<<"How many group generators ? ";cin>>r;for(intj=0;j<r;j++)g[j].input();SchreierSims();delete[]g;delete[]newg;delete[]cosrep;return0;}
海姆达尔——阿斯加德最伟大的儿子之一,众神和世界之树的守护者。自古以来古他的主要职责就是守卫阿斯嘉德的入口——一座世界之间的桥梁。现存唯一古老的技术是将一定数量的桥梁结合起来,创造出一座穿越中间世界的桥梁。例如:如果第一座桥将物质从世界 A 传输到世界 B,第二座桥——从 B 到 C,那么它们的组合可以直接将物质从世界 A 传输到世界 C. 而且,这个古老的技术甚至可以让你自己结合一座桥。海姆达尔想知道——使用他所知道的桥梁以及它们的组合,可以创造出多少不同的桥梁。输入两个整数 R,N 分别是海姆达尔发现的桥梁总数和宇宙中的世界数(1 \leqslant N \leqslant 15,1 \leqslant R \leqslant 1000)。接下来的 R 行包含这些桥的信息。每个桥由 N 个整数 a_{1}, a_{2},\cdots a_{n} 组成。其中 a_{i} 表示物质可以通过当前的桥梁转移到世界 i。如果当前的桥不影响那些世界,a_{i} = i。请输出一个可以通过古老技术建造的不同桥梁的总数。