本文主要是介绍组合数学--置换群，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj1721
题意：给出一个由n个数组成的经过m次置换（即把a[i]=a[a[i]]）后的群，求原来的那个群。
找出循环节 ----- 直接模拟！！
如 案列：n=7,m=4; 6 3 1 2 4 7 5
一次变化 7 1 6 3 2 5 4
二次变化 4 7 5 6 1 2 3
三次变化 6 3 1 2 4 7 5 ←到这里 即找到 循环节为 cnt=3；
那么原群就等于 m%=cnt; m=cnt-m; 从案列的数列经过m次循环就可以到 原群了！
#include<iostream>
#include<cstdio>
using namespace std;
#define N 1010
int a[N],b[N],c[N];
int n,m;
int solve()
{int ans=0;while(1){int i,j;ans++;for( i=1;i<=n;i++)b[i]=a[a[i]];for( j=1;j<=n;j++)if(c[j]!=b[j])break;if(j==n+1) break;for(int k=1;k<=n;k++)a[k]=b[k];}return ans;
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=c[i]=a[i];}int cnt=solve();m%=cnt;m=cnt-m;while(m--){for(int i=1;i<=n;i++)a[i]=c[c[i]];for(int j=1;j<=n;j++)c[j]=a[j];}for(int i=1;i<=n;i++)printf("%d\n",c[i]);}return 0;
}
poj3270
题意：给出一列数，求将这列数排成升序的最小花费，这里花费定义为交换两个数的和。
第一步：要求出每一个小轮换的循环节。
第二步：求一个小轮换最小值。
①：第一种方法：用这个轮换中的最小值，与每一个值交换。求出交换的和 sum1.
②：第二种方法：用整个数列中的最小值 与 这个轮换中的最小值交换，再执行①，最后再把最小值换回来。求的和.sum2.
③：求min（sum1,sum2）看哪个小！就把它加入答案中.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 10100
int MIN;
int n;
struct Node
{int temper;int id;bool operator<(const Node a) const{return temper<a.temper;}
}cow[N];
bool vis[N];
int solve()
{int cnt;int ans=0;memset(vis,false,sizeof(vis));for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=true;int sum=cow[i].temper;int m=cow[i].temper;int j=cow[i].id;cnt=0;while(i!=j){cnt++;vis[j]=true;sum+=cow[j].temper;if(m>cow[j].temper) {m=cow[j].temper;}j=cow[j].id;}ans+=min(sum-m+m*cnt,sum+m+MIN*(cnt+2));} }return ans;
}
int main()
{while(~scanf("%d",&n)){MIN=100000000;for(int i=1;i<=n;i++){scanf("%d",&cow[i].temper);cow[i].id=i;if(MIN>cow[i].temper) {MIN=cow[i].temper;}}sort(cow+1,cow+n+1);printf("%d\n",solve());}return 0;
}
poj2369
题解：多少步到单位群。
求出每个 轮换的 循环节 求最小公倍数就行了。
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 2005
int d[N];
int t[N],n;
void get_time(int i)
{int count=1;int j=d[i];while(i!=j){count++;j=d[j];}t[i]=count;
}
int gcd(int a,int b)
{if(!b) return a;else return gcd(b,a%b);
}
int lcm(int a,int b)
{return a/gcd(a,b)*b;
}
int _LCM()
{int ans=t[1];for(int i=2;i<=n;i++){ans=lcm(t[i],ans);}return ans;
}
int main()
{int i;while(~scanf("%d",&n)&&n){memset(d,0,sizeof(d));memset(t,0,sizeof(t));for(i=1;i<=n;i++){scanf("%d",&d[i]);}for(i=1;i<=n;i++)get_time(i);printf("%d\n",_LCM());}return 0;
}
poj1026
首先给出一个置换，然后给出一个字符串，问置换k次之后得到的字符串是什么？
同样的求出每个轮换的 循环节，然后k%循环节，求出这个轮换中每个元素的位置保存下来就行了。
#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 212
int n;
int key[N];
int t[N];
inline void get_time()
{int count=0;for(int i=1;i<=n;i++){count=1;int j=key[i];while(i!=j){count++;j=key[j];}t[i]=count;}
}
char res[N];
char str[N];
int main()
{while(~scanf("%d",&n)&&n){memset(t,0,sizeof(int)*(n+2));for(int i=1;i<=n;i++){scanf("%d",&key[i]);}get_time();int k;while(~scanf("%d",&k)&&k){getchar();gets(str+1);for (int i=strlen(str+1)+1;i<=n;i++) str[i]=' ';str[n+1]='\0';for(int i=1;i<=n;i++){int pos=i;for(int j=0;j<k%t[i];j++){pos=key[pos];}res[pos]=str[i];}res[n+1]='\0';printf("%s\n",res+1);}puts("");}return 0;
}
这篇关于组合数学--置换群的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
