组合数学实验.doc

组合数学实验 实验一 Cayley树的生成 源代码： import java.io.BufferedWriter; import java.io.FileWriter; import java.util.Scanner; public class Cayley { int n; long count; int a[][]; int b[][]; int s[][]; long func(int n1,int n2){ //求n1的n2次方 long m=1; while(n2=1){ m *=n1; n2--; } return m; } Cayley(int n0){ this.n=n0; this.count =this.func(n,n-2); s=new int[(int)count+1][n-1];//首先生成的 n-2 个元素的序列 a=new int[(int)count+1][n]; b=new int[(int)count+1][n]; int i,j; for(j=1;j=count;j++)//生成序列算法 { if((j%n)==0) s[j][1]=n; else s[j][1]=j%n; }//第1位 int f; //每一位取值1到7 long msize;//5^x int size; for(i=2;i=n-2;i++) { f=1; size=0; msize=this.func(n,i-1); for(j=1;j=count;j++) { if(size==msize) { if(f==n) { f=0; } f++; size=0; } s[j][i]=f; size++; }//for }//while//生成count个序列 ///////////////////////下面由s[i][j]生成 n-1对序列，每对序列由n-1条边表示，存于a[][],b[][]中 int a1[]=new int [n+1]; int b1[]=new int [n-1]; for(i=1;i=(int)count;i++) for(j=1;j=n-2;j++) b[i][j]=s[i][j]; for(i=1;i=(int)count;i++){ //每一个 int k; int k1; for(k=1;k=n-2;k++){ b1[k]=b[i][k]; }//得到本个的b1[] 1 for(int l=1;l=n;l++){ a1[l]=l;//得到本个的a1[] 2 } for(j=1;j=n-2;j++){ //每一个都要做这么多次计算 //每次 for(k=1;k=n-2;k++){ if(b1[k]!=0) { k1=b1[k]; a1[k1]=0; } }// 3 int min=n; int minCount=0; for(int p=1;p=n;p++){ if(a1[p]!=0 a1[p]min) { min=a1[p]; minCount=p; } }// 4 a[i][j]=min; a1[minCount]=0;// 5 int k2; k2=b1[j]; a1[k2]=k2; b1[j]=0;// 6 }//每一个都要做这么多次计算 end int q; for(q=1;q=n;q++){ if(a1[q]!=0){ a[i][n-1]=a1[q]; a1[q]=0; break; } } int