クラヴィッツの配列問題の考察(1)を示します。
考察(1)
●プログラム(ka111.c)
/* << ka111.c >> */ /* クラヴィッツの配列の生成。*/ #include <stdio.h> #include <stdlib.h> int m, /* 行mの値。*/ n, /* 列nの値。*/ count, /* 求める配置の個数。*/ p[99], /* 順列を保存する配列。*/ row[99], /* K番目数字が割り当てられる行番号。*/ col[99], /* K番目数字が割り当てられる列番号。*/ a[9][9]; /* 方眼紙を表す配列。*/ void perm(int k); int main() { int i,j,k; while( 1 ) { scanf("%d%d",&m,&n); if((m <= 0)&&(n <= 0)) { break; } /* 初期設定。*/ count=0; for( i=0; i<=m*n; i++ ) { p[i]=i; } /* 順列のk番目に対応する行番号row[k],列番号col[k]を求める。*/ row[0]=1; col[0]=1; for( k=1; k<=m*n; k++ ) { row[k]=(k-1)/n+1; col[k]=(k-1)%n+1; } /* m×nの方眼紙の初期設定。*/ for( i=0; i<=m; i++ ) { for( j=0; j<=n; j++ ) {a[i][j]=0; } } /* {1,2,…,mn}上の順列の生成。*/ perm(1); printf("配置の個数:%d",count); } } /* {1,2,…,mn}上の順列を生成する手続き。*/ /* kは順列におけるk番目の要素に対応する。*/ void perm(int k) { int i,j,x,y,w; /* 順列のk-1番目に対応する行番号x,列番号yを求める。*/ x=row[k-1]; y=col[k-1]; a[x][y]=p[k-1]; /* マス目(X,Y)の数が真下のマス目(X-1,Y)の数より小さい場合、戻る。*/ if(a[x][y] < a[x-1][y]) { return; } /* マス目(X,Y)の数が左隣のマス目(X,Y-1)の数より小さい場合、戻る。*/ if(a[x][y] < a[x][y-1]) { return; } if(k > m*n) { /* 解の表示。*/ count++; printf("[%d]\n",count); for( i=1; i<=m; i++ ) { for( j=1; j<=n; j++ ) { printf("%3d",a[i][j]); } printf("\n"); } printf("\n"); return; } /* つぎの位置の要素を指定する。*/ for( i=k; i<=m*n; i++ ) { w=p[k]; p[k]=p[i]; p[i]=w; perm(k+1); w=p[k]; p[k]=p[i]; p[i]=w; } }
実行結果