クラヴィッツの配列問題・考察（１）

　クラヴィッツの配列問題の考察（１）を示します。

考察（１）
f:id:isemba:20151208165759j:plain
●プログラム（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;
  }
}