置换(polya)代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】置换(polya)

作者:耀阳 / 发布于2016/4/21/ 591

//求置换的循环节,polya原理
//perm[0..n-1]为0..n-1的一个置换(排列)
//返回置换最小周期,num返回循环节个数
#define MAXN 1000

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

int polya(int* perm,int n,int& num){
	int i,j,p,v[MAXN]={0},ret=1;
	for (num=i=0;i<n;i++)
		if (!v[i]){
			for (num++,j=0,p=i;!v[p=perm[p]];j++)
				v[p]=1;
			ret*=j/gcd(ret,j);
		}
	return ret;
}

　　

试试其它关键字

同语言下

可能有用的

耀阳贡献的其它代码(13)

Copyright © 2004 - 2024 dezai.cn. All Rights Reserved 站长博客粤ICP备13059550号-3