【离散数学】置换群和伯恩赛德定理编程题

1：置换的轮换表示

给出一个置换，写出该置换的轮换表示。比如

(1 2 3 4 5 6 7 8 9)

(3 1 6 2 9 7 8 4 5)

表示为(1 3 6 7 8 4 2)(5 9)

输入：

置换后的序列

输出：

不相杂的轮换乘积，每行表示一个轮换（轮换的起始数字最小，每个轮换的起始数字递增排序，单轮换省略）

例如：

样例1：

输入：（空格分隔）

3 1 6 2 9 7 8 4 5

输出：

1 3 6 7 8 4 2（空格分隔）

5 9（空格分隔）

样例2：

输入：（空格分隔）

4 6 7 5 1 2 3

输出：

1 4 5（空格分隔）

2 6（空格分隔）

3 7 （空格分隔）

#include <cstdio>
#include <cstring>
int main()
{char c[50];gets(c); int n=(strlen(c)+1)/2;int i,j=0,k,flag=1,a[25],b[25];for(i=0;i<n;i++){a[i]=c[2*i]-48;b[i]=0;}int l=1;b[j]=l;printf("%d ",b[j]);j++;for(i=0;j<n;){if(a[i]==l)  //a[i]等于这一轮换的头，说明轮换结束 {printf("\n"); l++;   //找下一个轮换的头while(flag==1){for(k=0;k<j;k++){ if(l==b[k])  //l不能已经在之前的轮换中 {break;}}if(k==j)  //l不在轮换里 {if(l==a[l-1])  //单轮换不输出，还要接着找头不改变flag跳出while循环{b[j]=l;j++; if(j==n)  //如果单轮换是最后的数，就不用再找了，跳出while循环 {flag=0;}} else  //找到l了，可以跳出while循环{flag=0; b[j]=l;printf("%d ",b[j]);j++;i=l-1;} }else{l++;}}flag=1;   //给下一次找头做准备 }else  //a[i]不等于轮换的头 就继续加到轮换里{b[j]=a[i];printf("%d ",b[j]);j++;i=a[i]-1;}}return 0;
} 

2：轮换的复合运算

集合S中的元素个数小于10个,输入该集合的两个轮换t1和t2，计算两个轮换的乘积t（乘积采用左复合），输出的乘积结果t也表示为轮换。输入时每行输入一个不相交轮换ti（i=1,2）,输出的乘积为不相交轮换（单轮换省略不写）。

样例1：

输入： (注：数字和括号之间都没有空格,括号“(”和")"为半角英文)

(123)(456) （注：t1）

(245) （注：t2）

输出：

(1253)(46) （注：乘积t的每个轮换的起始数字是递增排序）

样例2：

输入： (注：数字和括号之间都没有空格,括号“(”和")"为半角英文)

(16)(23) (45)

(36)(125)

输出：

(13)(2456) （注：每个轮换的起始数字是递增排序）

样例3：

输入： (注：数字和括号之间都没有空格,括号“(”和")"为半角英文)

(2654)

(15)

输出：

(14265) （注：每个轮换的起始数字是递增排序）

样例4：

输入： (注：数字和括号之间都没有空格,括号“(”和")"为半角英文)

(1392)(475)

(267)

输出：

(13926547) （注：每个轮换的起始数字是递增排序）

#include <iostream>
#include <cstring>
using namespace std;
int b[20];
void work(int a[],int n){int j,i=0,k=0,num=1,count=n-3;printf("(1");int b[10]={0};while(k<count-1){if(a[i]!=i+1)printf("%d",a[i]);b[i]=1;k++;i=a[i]-1;if(a[i]==num){b[i]=1;k++;for(j=0;j<count-1;j++){if(b[j]==0){i=j;num=j+1;if(num!=a[i])printf(")(%d",num);break;}}}}printf(")");
}int main()
{char x[20],y[20];gets(x);gets(y);int i,j,k;int num1=0,num2=0,e=0,r=0;int count=0;int z[20]={0};for(i=1;i<11;i++)  //从1开始 {for(j=0;j<strlen(y);j++) //处理下面的轮换 {if(y[j]-'0' == i && y[j+1]!=')') //不等于末尾数 {num1=y[j+1]-'0';break;}if(y[j]-'0'==i && y[j+1]==')')  //等于末尾数 {int m=0;for(m=j;m>=0;m--){ if(y[m]=='(')  //找到该轮换的第一个数 {num1=y[m+1]-'0';e=1;break;}}if(e==1){break;}}num1=i;   //未找到这个数，即等于自身。 }for(k=0;k<strlen(x);k++){if(x[k]-'0'==num1 && x[k+1]!=')')   //不等于末位数 {num2=x[k+1]-'0';break;};if(x[k]-'0'==num1 && x[k+1]==')'){int m=0; for(m=k;m>=0;m--){if(x[m]=='('){num2=x[m+1]-'0';r=1;break;}}if(r==1){break;}};num2=num1;}e=0;r=0;z[count]=num2; count++;}work(z,count);
}
/*
int main(){char c[50];gets(c);char b[50];gets(b); int i,j,k,num1=0,num2=0,e=0,r=0,count=0;int arr[50]={0};for(i=1;i<11;i++){//start from 1for(j=0;j<strlen(b);j++){if(b[j]-'0'==i && b[i+1]!=')'){//非末尾的映射num1=b[j+1]-'0';break; } else if(b[j]-'0'==i && b[i+1]==')'){//末尾的映射int t;for(t=j;t>=0;t--){if(b[t]=='('){//轮换的第一个数num1=b[t+1]-'0';e=1;break; }}if(e==1){break;}}num1=i;//not found}for(k=0;k<strlen(c);k++){if(c[k]-'0'==num1 && c[k+1]!=')'){num2=c[k+1]-'0';break;}else if(c[k]-'0'==num1 && c[k+1]==')'){int t=0;for(t=k;t>=0;t--){if(c[t]=='('){num2=c[t+1]-'0';r=1;break;}}if(r==1){break;}}num2=num1;}e=0;r=0;arr[count++]=num2;}//arr [] , countcout<<("(1");int ret[10]={0};i=0;j=0;k=0;int n=count-3,num=1;while(k<n-1){if(arr[i]!=i+1){cout<<arr[i];}ret[i]=1;k++;i=arr[i]-1;if(arr[i]==num){ret[i]=1;k++;for(j=0;j<n-1;j++){if(ret[j]==0){i=j;num=j+1;if(num!=arr[i]){cout<<")("<<num;break;}}}}}cout<<")";return 0;
}
*/
好像给的案例最多只有两个划分区域
//    int len=strlen(c),heap[20],flag=0,cnt=0;
//    for(int i=0;i<len;i++){
//        if(c[i]=='('){
//            flag=1;
//            continue;
//        }
//        else if(c[i]==')'){
//            flag=0;
//            heap[cnt++]=-1;
//            //以-1分割 
//        }
//        //利用flag判断是否进数组
//        if(flag==1){
//            heap[cnt++]=c[i]-'0';
//        } 
//    }
//    
//    int lenb=strlen(b),heapb[20],flagb=0,cntb=0;
//    for(int i=0;i<lenb;i++){
//        if(b[i]=='('){
//            flagb=1;
//            continue;
//        }
//        else if(b[i]==')'){
//            flagb=0;
//            heapb[cntb++]=-1;
//            //以-1分割 
//        }
//        //利用flag判断是否进数组
//        if(flagb==1){
//            heapb[cntb++]=b[i]-'0';
//        } 
//    }
//    for(int i=0;i<cntb;i++){cout<<heapb[i]<<" ";}
//    
//    int max=-1;
//    for(int i=0;i<cnt;i++){
//        if(max<heap[i]){
//            max=heap[i];
//        }
//    }
//    for(int i=0;i<cntb;i++){
//        if(max<heapb[i]){
//            max=heapb[i];
//        }
//    }
//    //cout<<max;
//    
//    //开始映射（？）
//    int visit[max+1]={0};//标记是否visited
//    visit[0]=1;
//    while(1){
//        
//    }

3：脾气牛排队 Cow Sorting

Description

Farmer John's N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each cow has a unique "grumpiness" level in the range 1...100,000. Since grumpy cows are more likely to damage FJ's milking equipment, FJ would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (not necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes FJ a total of X+Y units of time to exchange two cows whose grumpiness levels are X and Y.

Please help FJ calculate the minimal time required to reorder the cows and give the procedure of sorting.

输入：

第1行：N (整数N代表牛的数量)

第2行到N+1行：牛的脾气值

输出：

第1行：最小排队代价值

第2行：给牛按脾气值升序排列的排队过程（每行表示一对交换，脾气值空格分隔）

样例：

输入：

7

6

7

4

5

3

2

1

输出：

33

6 1 4 5 3 2 7

6 2 4 5 3 1 7

1 2 4 5 3 6 7

1 2 4 3 5 6 7

1 2 3 4 5 6 7

#include <cstdio> 
int main()
{int i,j=0,k=1,flag=1,m,n,sum=0;int a[20],b[20],c[20][20];scanf("%d",&n); for(i=0;i<n;i++){scanf("%d",&a[i]);}int t=0,l=1;b[j] = l;j++;c[t][k] = l;k++;for(i=0;j<=n;){if(a[i]==l || j==n)  //a[i]等于这一轮换的头，或者b[]满了（所有数都进入了轮换），说明轮换结束{c[t][0] = k;  //c的每行第一个元素用来记录这个轮换的阶数+1if(c[t][1]*(k-2) > c[t][1]*2+k) //如果该轮换开头的，最小的数仍然很大（设为big），用big做k-2次对换的代价是big*(k-2)，先把1和big进行一次对换，用1去做k-2次兑换后再换回来代价是(1+big)*2+1*(k-2){int big = c[t][1];for(m=0;m<k;m++){ c[t+1][m] = c[t][m];  //把当前轮换往下挪一步}c[t][0] = 3;c[t][1] = 1;c[t][2] = c[t+1][1];   //加入一行轮换（对换） 把1和开头换一次c[t+1][1] = 1;   //把1换成该轮换的开头 sum += 1+big;t++;for(k--;k>1;k--){ sum += c[t][1]+c[t][k];  //代价加上对换的两个数}t++; c[t][0] = 3;c[t][1] = big;c[t][2] = 1;  //再加入一行轮换（对换） 把1和开头换回来sum += 1+big;}else{for(k--;k>1;k--)  //每个轮换都会被拆成k-1个对换{ sum += c[t][1]+c[t][k];  //代价加上对换的两个数}  } t++;l++;while(flag==1){for(m=0;m<j;m++){ if(l==b[m]){break;  //l不能已经在之前的轮换中 }}if(m==j)  //l不在轮换里 {if(l==a[l-1]){ b[j] = l;j++;  //单轮换不输出，还要接着找头不改变flag跳出while循环 if(j==n){flag = 0;  //如果单轮换是最后的数，就不用再找了，跳出while循环 } } else{flag = 0; b[j] = l;j++;c[t][k] = l;k++;i = l-1;} }else{l++;}}flag=1;  //给下一次找头做准备}else{ b[j] = a[i];j++;  //b记录出现在所有轮换里的数 c[t][k] = a[i];k++;  //c记录每一次轮换里的数 i = a[i]-1;}} printf("%d\n",sum);j=t;for(t=0;t<j;t++)  //把每个轮换c[t]拆成c[t][0]-1个对换{ for(k=c[t][0]-1;k>1;k--)  //对换c[t][1]和c[t][k]所代表的数在a[]中的位置{int x,y;  //x表示c[t][1]代表的数的位置；y表示c[t][k]代表的数的位置for(x=0;x<n;x++){if(a[x]==c[t][1]){break;}}for(y=0;y<n;y++){if(a[y]==c[t][k]){break;}}int t = a[y];a[y] = a[x];a[x] = t;for(m=0;m<n;m++)  //输出此次对换结果{printf("%d ",a[m]);}      printf("\n");}}  return 0;
}

4：洗牌机问题

Description

Alice and Bob have a set of N cards labelled with numbers 1 ... N (so that no two cards have the same label) and a shuffle machine. We assume that N is an odd integer.

The shuffle machine accepts the set of cards arranged in an arbitrary order and performs the following operation of double shuffle : for all positions i, 1 <= i <= N, if the card at the position i is j and the card at the position j is k, then after the completion of the operation of double shuffle, position i will hold the card k.

Alice and Bob play a game. Alice first writes down all the numbers from 1 to N in some random order: a1, a2, ..., aN. Then she arranges the cards so that the position ai holds the card numbered ai+1, for every 1 <= i <= N-1, while the position aN holds the card numbered a1.

This way, cards are put in some order x1, x2, ..., xN, where xi is the card at the ith position.

Now she sequentially performs S double shuffles using the shuffle machine described above. After that, the cards are arranged in some final order p1, p2, ..., pN which Alice reveals to Bob, together with the number S. Bob's task is to guess the order x1, x2, ..., xN in which Alice originally put the cards just before giving them to the shuffle machine.

Input

The first line of the input contains two integers separated by a single blank character : the odd integer N, 1 <= N <= 1000, the number of cards, and the integer S, 1 <= S <= 1000, the number of double shuffle operations.

The following N lines describe the final order of cards after all the double shuffles have been performed such that for each i, 1 <= i <= N, the (i+1)st line of the input file contains pi (the card at the position i after all double shuffles).

Output

The output should contain N lines which describe the order of cards just before they were given to the shuffle machine.

For each i, 1 <= i <= N, the ith line of the output file should contain xi (the card at the position i before the double shuffles).

样例1：

输入：

7 4

6

3

1

2

4

7

5

输出：

4

7

5

6

1

2

3

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<cmath>  
#define N 1003   
using namespace std;  int n,m;  
int cnt[N],a[N],ans[N],l[N],use[N],b[N];  int main(){  scanf("%d%d",&n,&m);  int maxn=0;int j,i;for(i=1;i<=n;i++){scanf("%d",&a[i]),cnt[i]=a[i];}  bool flag=1;  int t=0;while(1){t++;for(i=1;i<=n;i++){b[i]=a[a[i]];}for(i=1;i<=n;i++){if(cnt[i]!=b[i]) {flag=false;break;}}if(flag){break;}flag=true;for(int i=1;i<=n;i++){a[i]=b[i];}}for(i=1;i<=n;i++){a[i]=b[i];}t=t-m%t;for(i=1;i<=t;i++){for(j=1;j<=n;j++){b[j]=a[a[j]];}for(j=1;j<=n;j++){a[j]=b[j];}}for(i=1;i<=n;i++){printf("%d\n",a[i]);}return 0; 
}