組合せ等の最小完全ハッシュ関数とその逆変換(列挙)

このＣ／Ｃ＋＋言語で書かれたソースプログラムは、 組合せの整数化(組合せの辞書順での順位)と逆変換を行なう。
このうち整数化のことを、最小完全ハッシュ関数ともいう。
そして０から順に最大値までを逆変換すれば、 組合せ等を全て列挙することができる。
「いわゆる組合せ」「重複組合せ」「非負整数解」「順列」に対応している。

目次

• 応用例
• いわゆる組合せ(combination)
• 重複組合せ(repeated combination)
• 非負整数解(non-negative integer solutions)
• 順列(Permutation)

• INDEX を変更して大きな問題を解く
• マルチスレッドで使用する場合の注意
• テーブルを宣言して使用する場合
• r に対する最大の n の値と組合せの総数

古いバージョン

古いバージョン

• Ｃ言語の場合、 Init???_r( ) のパラメータに TBL_STATIC, TBL_STACK を追加
• Ｃ言語のために FreeCode( ) を追加した
• 組合せの要素の型を int から unsigned char にした
• CombToNumFast(), RepeToNumFast() を追加して NO_CODE_SORT を廃止した
• nCr 等の n と r の最大値が小さくなった
• 用語「分割組合せ(partition combination)」を 「非負整数解(non-negative integer solutions)」にした
• InitPart() から InitSolu() のように「非負整数解」の関数名の命名を Part から Solu にした
• エラーの原因を整数に加え文字列 CombErrMsg, RepeErrMsg, SoluErrMsg, PermErrMsg でも示すようにした

応用例

• 全組合せの列挙
• 一個の乱数からランダムな組合せを生成する
• 組合せの度数ソート
• 組合せの幅優先探索でハッシュ関数の代わりに使う

いわゆる組合せ(combination)

簡略版

例えぱ、0 1 2 3 4 のように 5 種類(cn=5,cn>=0)の要素があるものとし、 これから 3 つ要素(r=3,0<=r<=cn)を取り出す場合を考える。
取り出し方は 10 通りあって、辞書順での番号と組合せを列挙すると、

0:(0,1,2)  1:(0,1,3)  2:(0,1,4)  3:(0,2,3)  4:(0,2,4)
5:(0,3,4)  6:(1,2,3)  7:(1,2,4)  8:(1,3,4)  9:(2,3,4)

となる。ここでは(0,1,2)と(2,1,0)を同じものと考える。目的は、

以下に柔軟性のある正式版のプログラムを示す。

/* code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #if !defined(INDEX) #define INDEX unsigned #endif #if !defined(MAX_CODE_N) #if defined(_MSC_VER) #pragma warning(disable:4127) /* 条件式が定数です。 */ #endif #if defined(__TURBOC__) #pragma warn -ccc /* 条件が常に真・偽 */ #pragma warn -cln /* Constant is long */ #endif #define MAX_CODE_N 246 #define MAX_CODE_R 100 #define MAX_COMB_R MAX_CODE_R #define MAX_REPE_R MAX_CODE_R #define MAX_SOLU_R (MAX_CODE_R+1) #define MAX_PERM_N 256 #define MAX_PERM_R ( sizeof(INDEX)<=2?8:sizeof(INDEX)<=4?12:20 ) typedef enum { CEC_SUCCESS,CEC_MEMORY,CEC_OVERFLOW,CEC_PARAMETER } cec_t; typedef enum { TBL_UNKNOWN,TBL_STATIC=8,TBL_STACK } tbl_t; typedef enum { CT_UNKNOWN,CT_COMB,CT_REPE,CT_SOLU,CT_PERM } type_t; #if !defined(_MSC_VER) && !defined(__BORLANDC__) && !defined(__MINGW32__) #define __int64 long long #endif typedef struct tag_code { int n,r,bytes; cec_t errcode; tbl_t tbl; type_t type; INDEX*ptr,size; const char*errmsg; #if defined(__cplusplus) tag_code() { n=r=bytes=0; errcode=CEC_SUCCESS; tbl=TBL_UNKNOWN; type=CT_UNKNOWN; ptr=0; size=0; errmsg=0; } ~tag_code() { delete[]ptr; } #endif } code_t; #if defined(__cplusplus) #define TBL_OPT =TBL_STATIC #define FreeCode(P) \ do { delete[](P)->ptr; (P)->ptr=0; (P)->bytes=0; (P)->size=0; \ (P)->type=CT_UNKNOWN; } while (0) #else #define TBL_OPT #include <stdlib.h> #define FreeCode(P) \ do { free((P)->ptr); (P)->ptr=0; (P)->bytes=0; (P)->size=0; \ (P)->type=CT_UNKNOWN; } while (0) #endif #endif

/* comb.h いわゆる組合せの最小完全ハッシュ関数とその逆変換のヘッダファイル programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #if !defined(CombErrMsg) #include "code.h" extern code_t DefaultComb[1]; extern INDEX InitComb_r(code_t*const p,const int cn,const int r, const tbl_t t TBL_OPT); extern INDEX CombToNum_r(const code_t*const p,const unsigned char*const vec); extern void NumToComb_r (const code_t*const p,unsigned char*const vec,INDEX num); #define CombErrMsg (DefaultComb->errmsg) #define CombErrCode (DefaultComb->errcode) #define CombBytes (DefaultComb->bytes) #define CombTbl (DefaultComb->tbl) #define CombSize (DefaultComb->size) #define InitComb(cn,r) InitComb_r(DefaultComb,cn,r,TBL_STATIC) #define CombToNum(vec) CombToNum_r(DefaultComb,vec) #define CombToNumFast(vec) CombToNumFast_r(DefaultComb,vec) #define NumToComb(vec,num) NumToComb_r(DefaultComb,vec,num) #endif

/* comb.c いわゆる組合の最小完全ハッシュ関数とその逆変換のプログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include "comb.h" code_t DefaultComb[1]; INDEX InitComb_r(code_t*const p,const int cn,const int r,const tbl_t t) { int i,j; const int n=cn-r+1; INDEX*a[MAX_CODE_R],*b[MAX_CODE_R]; #ifdef __cplusplus if (p->type==CT_COMB&&p->size&&n==p->n&&r==p->r) return p->size; FreeCode(p); #else if (t==TBL_STATIC) { if (p->type==CT_COMB&&p->size&&n==p->n&&r==p->r) return p->size; FreeCode(p); } else p->ptr=0; #endif p->n=n; p->r=r; p->tbl=t; p->size=0; p->type=CT_COMB; p->errcode=CEC_PARAMETER; if (t!=TBL_STATIC&&t!=TBL_STACK) { p->errmsg="t!=TBL_STATIC:8 && t!=TBL_STACK:9"; return 0; } if (r<0) { p->errmsg="r < 0"; return 0; } if (n<=0) { p->errmsg="r > cn"; return 0; } if (r>MAX_CODE_R) { p->errmsg="r > MAX_CODE_R"; return 0; } if (n>MAX_CODE_N) { p->errmsg="cn >= MAX_CODE_N+r"; return 0; } p->errcode=CEC_SUCCESS; if (r==0) return p->size=1; p->errcode=CEC_MEMORY; p->errmsg="memory error"; #if defined(__cplusplus) try { p->ptr=new INDEX[n*r*2]; } catch(...) { p->ptr=0; } #else p->ptr=(INDEX*)calloc(n*r,2*sizeof(INDEX)); #endif if (p->ptr==0) return 0; p->bytes=n*r*2*(int)sizeof(INDEX); for (i=0;i<r;i++) { a[i]=p->ptr+i*n; b[i]=a[i]+n*r; } for (i=0;i<r;i++) a[i][n-1]=1; for (j=1;j<n;j++) a[r-1][j]=1; for (i=r-2;i>=0;i--) for (j=n-2;j>0;j--) a[i][j]=a[i][j+1]+a[i+1][j]; for (i=0;i<r;i++) a[i][0]=0; for (i=0;i<r;i++) for (j=1;j<n;j++) b[i][j-1]=a[i][j]+=a[i][j-1]; for (i=r-2;i>=0;i--) for (j=0;j<n-1;j++) b[i][j]+=b[i+1][j]; if (n==1) for (i=0;i<r;i++) b[i][0]=1; else for (i=0;i<r;i++) b[i][n-1]=b[i][n-2]+1; p->errcode=CEC_OVERFLOW; p->errmsg="Overflow"; for (i=0;i<r;i++) for (j=1;j<n;j++) if (b[i][j]<=b[i][j-1]) { FreeCode(p); return 0; } if (n>1&&b[0][n-1]-b[0][n-2]!=1) { FreeCode(p); return 0; } p->errcode=CEC_SUCCESS; p->errmsg=0; return p->size=b[0][n-1]; } INDEX CombToNum_r(const code_t*const p,const unsigned char*const vec) { int i,n=p->n,r=p->r; INDEX*a=p->ptr,num=0; int j; unsigned char k,sorted[MAX_CODE_R]; for (j=0;j<r;j++) { k=vec[j]; for (i=j;i>0&&sorted[i-1]>k;i--) sorted[i]=sorted[i-1]; sorted[i]=k; } for (i=0;i<r;i++,a+=n) num+=a[sorted[i]-i]; return num; } INDEX CombToNumFast_r(const code_t*const p,const unsigned char*const vec) { int i,n=p->n,r=p->r; INDEX*a=p->ptr,num=0; for (i=0;i<r;i++,a+=n) num+=a[vec[i]-i]; return num; } void NumToComb_r(const code_t*const p,unsigned char*const vec,INDEX num) { int i,j=0,n=p->n,r=p->r; INDEX*a=p->ptr,*b=a+n*r; for (i=0;i<r;i++,a+=n,b+=n) { while (b[j]<=num) j++; num-=a[j]; vec[i]=(unsigned char)(j+i); } }

/* test-c.c いわゆる組合せの最小完全ハッシュ関数とその逆変換 comb.c のテスト programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #include <string.h> #include "comb.c" #define SCR 23 /* 画面の行数 */ int main(void) { int i,j,err=0,cn=5,r=3,an; unsigned*a,*b,s,sz=InitComb(cn,r); unsigned char vec[MAX_COMB_R],prev[MAX_COMB_R]; if (sz==0) { printf("Error InitComb(cn=%d,r=%d) %s\n",cn,r,CombErrMsg); return 1; } for (s=0;s<sz;s++) { NumToComb(vec,s); printf("%4u -> (",s); if (r>0) printf("%u",vec[0]); else printf("-"); for (i=1;i<r;i++) printf(",%u",vec[i]); printf(") ->%4u\n", CombToNumFast(vec)); } printf(" HIT [ENTER] KEY > "); fgetc(stdin); printf("Combination(cn,r):checking ...\n "); for (r=0;r<=11;r++) printf(" r=%2d",r); printf("\n"); for (cn=0;cn<=18;cn++) { printf("cn=%2d",cn); for (r=0;r<=(cn>11?11:cn);r++) { sz=InitComb(cn,r); if (sz==0) { err++; continue; } printf("%6u",sz); for (s=0;s<sz;s++) { NumToComb(vec,s); /* 小さい順かのテスト */ for (j=1;j<r;j++) if (vec[j-1]>=vec[j]) err++; /* 辞書順で前の結果より大きいかどうかのテスト */ if (s>=1&&memcmp(prev,vec,r)>=0) err++; memcpy(prev,vec,r); /* 逆変換で元に戻るかのテスト */ if (CombToNumFast(vec)!=s) err++; for (j=0;j<r/2;j++) { unsigned char t=vec[j]; vec[j]=vec[r-j-1]; vec[r-j-1]=t; } if (CombToNum(vec)!=s) err++; } } printf("\n"); } printf("ErrorCount=%d >",err); fgetc(stdin); for (cn=0;cn<=9;cn++) { for (r=0;r<=cn;r++) { sz=InitComb(cn,r); if (sz==0) continue; for (i=0;i<10;i++) printf("\n"); printf(" InitComb(cn,r)=(%d,%d) size=%u\n",cn,r,sz); a=DefaultComb->ptr; an=cn-r+1; b=a+an*r; for (i=0;i<r;i++) { if (i==0) printf("a:"); else printf(" "); for (j=0;j<an;j++) printf("%4u",a[j]); printf(" "); if (i==0) printf("b:"); else printf(" "); for (j=0;j<an;j++) printf("%4u",b[j]); printf("\n"); a+=an; b+=an; } if ((int)sz>SCR-1-r) sz=(unsigned)(SCR-1-r); for (s=0;s<sz;s++) { NumToComb(vec,s); printf(" num=%-2u : ",s); if (r) { printf("vec[]={%u",vec[0]); for (j=1;j<r;j++) printf(",%u",vec[j]); printf("}\n"); } else printf("No Change\n"); } for (i=0;i<SCR-1-r-(int)sz;i++) printf("\n"); printf(" HIT [ENTER] KEY > "); fgetc(stdin); } } return 0; }

結果の最初は以下のようになる。

   0 -> (0,1,2) ->   0
   1 -> (0,1,3) ->   1
   2 -> (0,1,4) ->   2
   3 -> (0,2,3) ->   3
   4 -> (0,2,4) ->   4
   5 -> (0,3,4) ->   5
   6 -> (1,2,3) ->   6
   7 -> (1,2,4) ->   7
   8 -> (1,3,4) ->   8
   9 -> (2,3,4) ->   9

InitComb(cn,r) は2つの引数をともなう(cn=5,r=3)。
InitComb(cn,r) は入力された cn と r が正しいかどうか検査する。
cn と r が正しくない場合、例えば、(cn=5,r=6) ならエラーとなり０を返す。

さらに、組合せの計算のときに、cn と r が大きすぎて、 unsigned の範囲を超えオーバーフローを起こしたときもエラーとなり０を返す。

cn と r が正しい場合、InitComb(cn,r) は組合せが何通りあるかを返す。
例えば、InitComb(5,3)の場合は 10 を返す。
InitComb(cn,r)は、また、CombToNum(vec), CombToNumFast(vec), NumToComb(vec,num) を高速に計算するのに必要な内部テーブルを設定する。

NumToComb(vec,num) は、unsigned num で与えられた辞書順での番号から、 unsigned char vec[] へ取り出し方を展開する。
num は、0 以上 InitComb(cn,r) 未満である。

CombToNum(vec) は、unsigned char vec[] で与えられた取り出し方から 0 以上 InitComb(cn,r) 未満の辞書順での番号を unsigned で返す。
vec[] は昇順でなくてもよい。

CombToNumFast(vec) は、unsigned char vec[] で与えられた取り出し方から 0 以上 InitComb(cn,r) 未満の辞書順での番号を unsigned で返す。
vec[] は常に昇順である必要がある。

性能は、例えばロト６のような場合(cn=43,r=6)、 NumToComb( ) の一億回の実行で 7.467 秒。
CombToNum( ) の一億回の実行で 1.171 秒となった。
CombToNumFast( ) の一億回の実行で 0.562 秒。
(Core i5-10210U、Visual C++ 2008)

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

comb.h いわゆる組合せの最小完全ハッシュ関数とその逆変換のヘッダファイル

comb.c いわゆる組合せの最小完全ハッシュ関数とその逆変換のプログラム

/* speed.c 最小完全ハッシュ関数とその逆変換の性能測定共通プログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <limits.h> #define SIZE 4000 #if INT_MAX <= 32767 #define INDEX unsigned long #endif #if defined(MSDOS_EXE) && INT_MAX <= 32767 #define ITER_STR "1,000,000 " #define ITER_NUM (1000000L/SIZE) #elif INT_MAX <= 32767 #define ITER_STR "10,000,000 " #define ITER_NUM (10000000L/SIZE) #else #define ITER_STR "100,000,000 " #define ITER_NUM (100000000L/SIZE) #endif #if INT_MAX <= 32767 long Tick(void) { static long next,add; long prev; do { prev=next; if (*(char far*)0x00400070L) { *(char far*)0x00400070L=0; add+=1573040L; } next=*(long far*)0x0040006cL+add; } while (prev!=next); return next; } #define TICK_PER_SEC 18.20648 #else #include <time.h> #if defined(__unix__) long Tick(void) { struct timespec t; clock_gettime(CLOCK_REALTIME,&t); return(long)(t.tv_sec*1000+(long)t.tv_nsec/1000000); } #define TICK_PER_SEC 1000.0 #else #define Tick() ((long)(clock())) #define TICK_PER_SEC CLOCKS_PER_SEC #endif #endif unsigned long NextRand32(void) { static unsigned long y=2463534242UL; y^=y<<13; y^=y>>17; return(y^=y<<5)&0xffffffffUL; }

/* speed-c.c 組合せの最小完全ハッシュ関数とその逆変換の性能測定プログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #include "speed.c" #include "comb.c" #define CN 43 #define R 6 INDEX Source[SIZE],Sum; unsigned char Results[SIZE][R]; int main(void) { INDEX sz=InitComb(CN,R); long clo,k; int i; if (sz==0) { printf("Error InitComb(CN=%d,R=%d) %s\n",CN,R,CombErrMsg); return 1; } for (i=0;i<SIZE;i++) Source[i]=(INDEX)(NextRand32()%sz); printf("InitComb(%d,%d)=%.0f\n",CN,R,(double)sz); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) NumToComb(Results[i],Source[i]); printf(ITER_STR "NumToComb() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC) ); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) Sum+=CombToNum(Results[i]); printf(ITER_STR "CombToNum() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC)); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) Sum+=CombToNumFast(Results[i]); printf(ITER_STR "CombToNumFast() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC)); return 0; }

重複組合せ(repeated combination)

簡略版

例えぱ、0 1 2 のように 3 種類(n=3,n>0)の要素があるものとし、 これから 3 つ要素(r=3,r>=0)を取り出す場合を考える。
ただし、同じ要素を複数個取り出してもよいとする。
取り出し方は、10 通りあって、辞書順での番号と組合せを列挙すると、

0:(0,0,0)  1:(0,0,1)  2:(0,0,2)  3:(0,1,1)  4:(0,1,2)
5:(0,2,2)  6:(1,1,1)  7:(1,1,2)  8:(1,2,2)  9:(2,2,2)

となる。ここでは(0,1,2)と(2,1,0)を同じものと考える。目的は、

以下に柔軟性のある正式版のプログラムを示す。

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

/* repe.h 重複組合せの最小完全ハッシュ関数とその逆変換のヘッダファイル programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #if !defined(RepeErrMsg) #include "code.h" extern code_t DefaultRepe[1]; extern INDEX InitRepe_r(code_t*const p,const int n,const int r, const tbl_t t TBL_OPT); extern INDEX RepeToNum_r(const code_t*const p,const unsigned char*const vec); extern void NumToRepe_r (const code_t*const p,unsigned char*const vec,INDEX num); #define RepeErrMsg (DefaultRepe->errmsg) #define RepeErrCode (DefaultRepe->errcode) #define RepeBytes (DefaultRepe->bytes) #define RepeTbl (DefaultRepe->tbl) #define RepeSize (DefaultRepe->size) #define InitRepe(n,r) InitRepe_r(DefaultRepe,n,r,TBL_STATIC) #define RepeToNum(vec) RepeToNum_r(DefaultRepe,vec) #define RepeToNumFast(vec) RepeToNumFast_r(DefaultRepe,vec) #define NumToRepe(vec,num) NumToRepe_r(DefaultRepe,vec,num) #endif

/* repe.c 重複組合せの最小完全ハッシュ関数とその逆変換のプログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include "repe.h" code_t DefaultRepe[1]; INDEX InitRepe_r(code_t*const p,const int n,const int r,const tbl_t t) { int i,j; INDEX*a[MAX_CODE_R],*b[MAX_CODE_R]; #ifdef __cplusplus if (p->type==CT_REPE&&p->size&&n==p->n&&r==p->r) return p->size; FreeCode(p); #else if (t==TBL_STATIC) { if (p->type==CT_REPE&&p->size&&n==p->n&&r==p->r) return p->size; FreeCode(p); } else p->ptr=0; #endif p->n=n; p->r=r; p->tbl=t; p->type=CT_REPE; p->errcode=CEC_PARAMETER; if (t!=TBL_STATIC&&t!=TBL_STACK) { p->errmsg="t!=TBL_STATIC:8 && t!=TBL_STACK:9"; return 0; } if (r<0) { p->errmsg="r < 0"; return 0; } if (n<=0) { p->errmsg="n <= 0"; return 0; } if (r>MAX_CODE_R) { p->errmsg="r > MAX_CODE_R"; return 0; } if (n>MAX_CODE_N) { p->errmsg="n > MAX_CODE_N"; return 0; } p->errcode=CEC_SUCCESS; if (r==0) return p->size=1; p->errcode=CEC_MEMORY; p->errmsg="memory error"; #if defined(__cplusplus) try { p->ptr=new INDEX[n*r*2]; } catch(...) { p->ptr=0; } #else p->ptr=(INDEX*)calloc(n*r,2*sizeof(INDEX)); #endif if (p->ptr==0) return 0; p->bytes=n*r*2*(int)sizeof(INDEX); for (i=0;i<r;i++) { a[i]=p->ptr+i*n; b[i]=a[i]+n*r; } for (i=0;i<r;i++) a[i][n-1]=1; for (j=1;j<n;j++) a[r-1][j]=1; for (i=r-2;i>=0;i--) for (j=n-2;j>0;j--) a[i][j]=a[i][j+1]+a[i+1][j]; for (i=0;i<r;i++) a[i][0]=0; for (i=0;i<r;i++) for (j=1;j<n;j++) b[i][j-1]=a[i][j]+=a[i][j-1]; for (i=r-2;i>=0;i--) for (j=0;j<n-1;j++) b[i][j]+=b[i+1][j]; if (n==1) for (i=0;i<r;i++) b[i][0]=1; else for (i=0;i<r;i++) b[i][n-1]=b[i][n-2]+1; p->errcode=CEC_OVERFLOW; p->errmsg="Overflow"; for (i=0;i<r;i++) for (j=1;j<n;j++) if (b[i][j]<=b[i][j-1]) { FreeCode(p); return 0; } if (n>1&&b[0][n-1]-b[0][n-2]!=1) { FreeCode(p); return 0; } p->errcode=CEC_SUCCESS; p->errmsg=0; return p->size=b[0][n-1]; } INDEX RepeToNum_r(const code_t*const p,const unsigned char*const vec) { int i,n=p->n,r=p->r; INDEX*a=p->ptr,num=0; int j; unsigned char k,sorted[MAX_CODE_R]; for (j=0;j<r;j++) { k=vec[j]; for (i=j;i>0&&sorted[i-1]>k;i--) sorted[i]=sorted[i-1]; sorted[i]=k; } for (i=0;i<r;i++,a+=n) num+=a[sorted[i]]; return num; } INDEX RepeToNumFast_r(const code_t*const p,const unsigned char*const vec) { int i,n=p->n,r=p->r; INDEX*a=p->ptr,num=0; for (i=0;i<r;i++,a+=n) num+=a[vec[i]]; return num; } void NumToRepe_r(const code_t*const p,unsigned char*const vec,INDEX num) { int i,j=0,n=p->n,r=p->r; INDEX*a=p->ptr,*b=a+n*r; for (i=0;i<r;i++,a+=n,b+=n) { while (b[j]<=num) j++; num-=a[j]; vec[i]=(unsigned char)j; } }

/* test-r.c 重複組合せの最小完全ハッシュ関数とその逆変換 repe.c のテスト programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #include <string.h> #include "repe.c" #define SCR 23 /* 画面の行数 */ int main(void) { int i,j,err=0,n=3,r=3; unsigned*a,*b,s,sz=InitRepe(n,r); unsigned char vec[MAX_REPE_R],prev[MAX_REPE_R]; if (sz==0) { printf("Error InitRepe(n=%d,r=%d) %s\n",n,r,RepeErrMsg); return 1; } for (s=0;s<sz;s++) { NumToRepe(vec,s); printf("%4u -> (",s); if (r>0) printf("%u",vec[0]); else printf("-"); for (i=1;i<r;i++) printf(",%u",vec[i]); printf(") ->%4u\n",RepeToNumFast(vec)); } printf(" HIT [ENTER] KEY > "); fgetc(stdin); printf("Repeated(n,r):checking ...\n "); for (r=0;r<=9;r++) printf(" r=%2d",r); printf("\n"); for (n=1;n<=10;n++) { printf("n=%2d",n); for (r=0;r<=9;r++) { sz=InitRepe(n,r); if (sz==0) { err++; continue; } printf("%7u",sz); for (s=0;s<sz;s++) { NumToRepe(vec,s); /* 小さい順かのテスト */ for (j=1;j<r;j++) if (vec[j-1]>vec[j]) err++; /* 辞書順で前の結果より大きいかどうかのテスト */ if (s>=1&&memcmp(prev,vec,r)>=0) err++; memcpy(prev,vec,r); /* 逆変換で元に戻るかのテスト */ if (RepeToNumFast(vec)!=s) err++; for (j=0;j<r/2;j++) { unsigned char t=vec[j]; vec[j]=vec[r-j-1]; vec[r-j-1]=t; } if (RepeToNum(vec)!=s) err++; } } printf("\n"); } printf("ErrorCount=%d >",err); fgetc(stdin); for (n=1;n<=6;n++) { for (r=0;r<=6;r++) { sz=InitRepe(n,r); if (sz==0) continue; for (i=0;i<10;i++) printf("\n"); printf(" InitRepe(n,r)=(%d,%d) size=%u\n",n,r,sz); a=DefaultRepe->ptr; b=a+n*r; for (i=0;i<r;i++) { if (i==0) printf("a:"); else printf(" "); for (j=0;j<n;j++) printf("%4u",a[j]); printf(" "); if (i==0) printf("b:"); else printf(" "); for (j=0;j<n;j++) printf("%4u",b[j]); printf("\n"); a+=n,b+=n; } if ((int)sz>SCR-r) sz=(unsigned)(SCR-r); for (s=0;s<sz;s++) { NumToRepe(vec,s); printf(" num=%-2u : ",s); if (r) { printf("vec[]={%u",vec[0]); for (j=1;j<r;j++) printf(",%u",vec[j]); printf("}\n"); } else printf("No Change\n"); } for (i=0;i<SCR-r-(int)sz;i++) printf("\n"); printf(" HIT [ENTER] KEY > "); fgetc(stdin); } } return 0; }

結果の最初は以下のようになる。

   0 -> (0,0,0) ->   0
   1 -> (0,0,1) ->   1
   2 -> (0,0,2) ->   2
   3 -> (0,1,1) ->   3
   4 -> (0,1,2) ->   4
   5 -> (0,2,2) ->   5
   6 -> (1,1,1) ->   6
   7 -> (1,1,2) ->   7
   8 -> (1,2,2) ->   8
   9 -> (2,2,2) ->   9

InitRepe(n,r) は2つの引数をともなう(n=3,r=3)。
InitRepe(n,r) は入力された n と r が正しいかどうか検査する。
n と r が正しくない場合、例えば、(n=0,r=0) ならエラーとなり０を返す。

さらに、組合せの計算のときに、n と r が大きすぎて、 unsigned の範囲を超えオーバーフローを起こしたときもエラーとなり０を返す。
０を返した場合、整数 RepeErrCode と文字列 RepeErrMsg に原因が示される。

n と r が正しい場合、InitRepe(n,r) は組合せが何通りあるかを返す。
例えば、InitSolu(3,3)の場合は 10 を返す。
InitRepe(n,r)は、また、RepeToNum(vec), RepeToNumFast(vec), NumToRepe(vec,num) を高速に計算するのに必要な内部テーブルを設定する。

NumToRepe(vec,num) は、unsigned num で与えられた辞書順での番号から、 unsigned char vec[] へ取り出し方を展開する。
num は、0 以上 InitRepe(n,r) 未満である。

RepeToNum(vec) は、unsigned char vec[] で与えられた取り出し方から 0 以上 InitRepe(n,r) 未満の辞書順での番号を unsigned で返す。
vec[] は昇順でなくてもよい。

RepeToNumFast(vec) は、unsigned char vec[] で与えられた取り出し方から 0 以上 InitRepe(n,r) 未満の辞書順での番号を unsigned で返す。
vec[] は常に昇順である必要がある。

性能は、例えば speed-c.c と同じ規模(n=38,r=6)の場合、 NumToRepe( ) の一億回の実行で 7.451 秒。
RepeToNum( ) の一億回の実行で 1.125 秒となった。
RepeToNumFast( ) の一億回の実行で 0.515 秒。
(Core i5-10210U、Visual C++ 2008)

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

repe.h 重複組合せの最小完全ハッシュ関数とその逆変換のヘッダファイル

repe.c 重複組合せの最小完全ハッシュ関数とその逆変換のプログラム

speed.c 最小完全ハッシュ関数とその逆変換の性能測定共通プログラム

/* speed-r.c 重複組合せの最小完全ハッシュ関数とその逆変換の性能測定プログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #include "speed.c" #include "repe.c" #define N 38 #define R 6 INDEX Source[SIZE],Sum; unsigned char Results[SIZE][R]; int main(void) { INDEX sz=InitRepe(N,R); long clo,k; int i; if (sz==0) { printf("Error InitRepe(N=%d,R=%d) %s\n",N,R,RepeErrMsg); return 1; } for (i=0;i<SIZE;i++) Source[i]=(INDEX)(NextRand32()%sz); printf("InitRepe(%d,%d)=%.0f\n",N,R,(double)sz); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) NumToRepe(Results[i],Source[i]); printf(ITER_STR "NumToRepe() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC) ); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) Sum+=RepeToNum(Results[i]); printf(ITER_STR "RepeToNum() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC)); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) Sum+=RepeToNumFast(Results[i]); printf(ITER_STR "RepeToNumFast() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC)); return 0; }

非負整数解(non-negative integer solutions)

簡略版

例えぱ、3 個の球(sn=3,sn>=0)があるものとし、 これを 3 つの箱(sr=3,sr>0)に分ける場合を考える
分け方は、10 通りあって、辞書順での番号と組合せを列挙すると、

0:(0,0,3)  1:(0,1,2)  2:(0,2,1)  3:(0,3,0)  4:(1,0,2)
5:(1,1,1)  6:(1,2,0)  7:(2,0,1)  8:(2,1,0)  9:(3,0,0)

となる。

非負整数の配列 X は、方程式 X[0]+X[1]+X[2]=3 の解である。

(非負整数解の数は rHn であるがこれは n+1Hr-1 に等しい。
なぜなら nHr=n+r-1Cr であり nCr=nCn-r だからである。)

目的は、

以下に柔軟性のある正式版のプログラムを示す。

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

/* solu.h 非負整数解の最小完全ハッシュ関数とその逆変換のヘッダファイル programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #if !defined(SoluErrMsg) #include "code.h" extern code_t DefaultSolu[1]; extern INDEX InitSolu_r(code_t*const p,const int sn,const int sr, const tbl_t t TBL_OPT); extern INDEX SoluToNum_r(const code_t*const p,const unsigned char*const vec); extern void NumToSolu_r (const code_t*const p,unsigned char*const vec,INDEX num); #define SoluErrMsg (DefaultSolu->errmsg) #define SoluErrCode (DefaultSolu->errcode) #define SoluBytes (DefaultSolu->bytes) #define SoluTbl (DefaultSolu->tbl) #define SoluSize (DefaultSolu->size) #define InitSolu(sn,sr) InitSolu_r(DefaultSolu,sn,sr,TBL_STATIC) #define SoluToNum(vec) SoluToNum_r(DefaultSolu,vec) #define NumToSolu(vec,num) NumToSolu_r(DefaultSolu,vec,num) #endif

/* solu.c 非負整数解の最小完全ハッシュ関数とその逆変換のプログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include "solu.h" code_t DefaultSolu[1]; INDEX InitSolu_r(code_t*const p,const int sn,const int sr,const tbl_t t) { int i,j; const int n=sn+1,r=sr-1; INDEX*a[MAX_CODE_R],*b[MAX_CODE_R]; #ifdef __cplusplus if (p->type==CT_SOLU&&p->size&&n==p->n&&r==p->r) return p->size; FreeCode(p); #else if (t==TBL_STATIC) { if (p->type==CT_SOLU&&p->size&&n==p->n&&r==p->r) return p->size; FreeCode(p); } else p->ptr=0; #endif p->n=n; p->r=r; p->tbl=t; p->size=0; p->type=CT_SOLU; p->errcode=CEC_PARAMETER; if (t!=TBL_STATIC&&t!=TBL_STACK) { p->errmsg="t!=TBL_STATIC:8 && t!=TBL_STACK:9"; return 0; } if (r<0) { p->errmsg="sr <= 0"; return 0; } if (n<=0) { p->errmsg="sn < 0"; return 0; } if (r>MAX_CODE_R) { p->errmsg="sr > MAX_CODE_R+1"; return 0; } if (n>MAX_CODE_N) { p->errmsg="sn >= MAX_CODE_N"; return 0; } p->errcode=CEC_SUCCESS; if (r==0) return p->size=1; p->errcode=CEC_MEMORY; p->errmsg="memory error"; #if defined(__cplusplus) try { p->ptr=new INDEX[n*r*2]; } catch(...) { p->ptr=0; } #else p->ptr=(INDEX*)calloc(n*r,2*sizeof(INDEX)); #endif if (p->ptr==0) return 0; p->bytes=n*r*2*(int)sizeof(INDEX); for (i=0;i<r;i++) { a[i]=p->ptr+i*n; b[i]=a[i]+n*r; } for (i=0;i<r;i++) a[i][n-1]=1; for (j=1;j<n;j++) a[r-1][j]=1; for (i=r-2;i>=0;i--) for (j=n-2;j>0;j--) a[i][j]=a[i][j+1]+a[i+1][j]; for (i=0;i<r;i++) a[i][0]=0; for (i=0;i<r;i++) for (j=1;j<n;j++) b[i][j-1]=a[i][j]+=a[i][j-1]; for (i=r-2;i>=0;i--) for (j=0;j<n-1;j++) b[i][j]+=b[i+1][j]; if (n==1) for (i=0;i<r;i++) b[i][0]=1; else for (i=0;i<r;i++) b[i][n-1]=b[i][n-2]+1; p->errcode=CEC_OVERFLOW; p->errmsg="Overflow"; for (i=0;i<r;i++) for (j=1;j<n;j++) if (b[i][j]<=b[i][j-1]) { FreeCode(p); return 0; } if (n>1&&b[0][n-1]-b[0][n-2]!=1) { FreeCode(p); return 0; } p->errcode=CEC_SUCCESS; p->errmsg=0; return p->size=b[0][n-1]; } INDEX SoluToNum_r(const code_t*const p,const unsigned char*const vec) { int i,z=0,n=p->n,r=p->r; INDEX*a=p->ptr,num=0; for (i=0;i<r;i++,a+=n) num+=a[z+=vec[i]]; return num; } void NumToSolu_r(const code_t*const p,unsigned char*const vec,INDEX num) { int i,j=0,n=p->n,r=p->r,sum=n-1,prev=0; INDEX*a=p->ptr,*b=a+n*r; for (i=0;i<r;i++,a+=n,b+=n) { while (b[j]<=num) j++; num-=a[j]; sum-=vec[i]=(unsigned char)(j-prev); prev=j; } vec[i]=(unsigned char)sum; }

/* test-s.c 非負整数解の最小完全ハッシュ関数とその逆変換 solu.c のテスト programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #include <string.h> #include "solu.c" #define SCR 23 /* 画面の行数 */ int main(void) { int i,j,err=0,sn=3,sr=3,sum; unsigned*a,*b,s,sz=InitSolu(sn,sr); unsigned char vec[MAX_SOLU_R],prev[MAX_SOLU_R]; if (sz==0) { printf("Error InitSolu(sn=%d,sr=%d) %s\n",sn,sr,SoluErrMsg); return 1; } for (s=0;s<sz;s++) { NumToSolu(vec,s); printf("%4u -> (%u", s,vec[0]); for (i=1;i<sr;i++) printf(",%u",vec[i]); printf(") ->%4u\n", SoluToNum(vec)); } printf(" HIT [ENTER] KEY > "); fgetc(stdin); printf("Solutions(sn,sr):checking ...\n "); for (sr=1;sr<=10;sr++) printf(" sr=%2d",sr); printf("\n"); for (sn=0;sn<=9;sn++) { printf("sn=%2d",sn); for (sr=1;sr<=10;sr++) { sz=InitSolu(sn,sr); if (sz==0) { err++; continue; } printf("%7u",sz); for (s=0;s<sz;s++) { NumToSolu(vec,s); /* 合計がｎになっているかどうかのテスト */ for (sum=j=0;j<sr;j++) sum+=vec[j]; if (sum!=sn) err++; /* 辞書順で前の結果より大きいかどうかのテスト */ if (s>=1&&memcmp(prev,vec,sr)>=0) err++; memcpy(prev,vec,sr); /* 逆変換で元に戻るかのテスト */ if (SoluToNum(vec)!=s) err++; } } printf("\n"); } printf("ErrorCount=%d >",err); fgetc(stdin); for (sn=0;sn<=6;sn++) { for (sr=1;sr<=6;sr++) { sz=InitSolu(sn,sr); if (sz==0) continue; for (i=0;i<10;i++) printf("\n"); printf(" InitSolu(sn,sr)=(%d,%d) size=%u\n",sn,sr,sz); a=DefaultSolu->ptr; b=a+(sn+1)*(sr-1); for (i=0;i<sr-1;i++) { if (i==0) printf("a:"); else printf(" "); for (j=0;j<=sn;j++) printf("%4u",a[j]); printf(" "); if (i==0) printf("b:"); else printf(" "); for (j=0;j<=sn;j++) printf("%4u",b[j]); printf("\n"); a+=sn+1,b+=sn+1; } if ((int)sz>SCR-sr) sz=(unsigned)(SCR-sr); for (s=0;s<sz;s++) { NumToSolu(vec,s); printf(" num=%-2u : ",s); if (sr) { printf("vec[]={%u",vec[0]); for (j=1;j<sr;j++) printf(",%u",vec[j]); printf("}\n"); } else printf("No Change\n"); } for (i=0;i<SCR-sr-(int)sz;i++) printf("\n"); printf(" HIT [ENTER] KEY > "); fgetc(stdin); } } return 0; }

結果の最初は以下のようになる。

   0 -> (0,0,3) ->   0
   1 -> (0,1,2) ->   1
   2 -> (0,2,1) ->   2
   3 -> (0,3,0) ->   3
   4 -> (1,0,2) ->   4
   5 -> (1,1,1) ->   5
   6 -> (1,2,0) ->   6
   7 -> (2,0,1) ->   7
   8 -> (2,1,0) ->   8
   9 -> (3,0,0) ->   9

InitSolu(sn,sr) は2つの引数をともなう(sn=3,s=3)。
InitSolu(n,r) は入力された n と r が正しいかどうか検査する。
sn と sr が正しくない場合、例えば、(sn=0,sr=0) ならエラーとなり０を返す。

さらに、組合せの計算のときに、sn と sr が大きすぎて、 unsigned の範囲を超えオーバーフローを起こしたときもエラーとなり０を返す。
０を返した場合、整数 SoluErrCode と文字列 SoluErrMsg に原因が示される。

sn と sr が正しい場合、InitSolu(sn,sr) は組合せが何通りあるかを返す。
例えば、InitSolu(3,3)の場合は 10 を返す。
InitSolu(sn,sr)は、また、SoluToNum(vec), NumToSolu(vec,num) を高速に計算するのに必要な内部テーブルを設定する。

NumToSolu(vec,num) は、unsigned num で与えられた辞書順での番号から、 unsigned char vec[] へ取り出し方を展開する。
num は、0 以上 InitSolu(sn,sr) 未満である。

SoluToNum(vec) は、unsigned char vec[] で与えられた取り出し方から 0 以上 InitSolu(sn,sr) 未満の辞書順での番号を unsigned で返す。

性能は、例えば speed-c.c と同じ規模(sn=37,r=7)の場合、 NumToSolu( ) の一億回の実行で 8.044 秒。
SoluToNum( ) の一億回の実行で 0.657 秒。
(Core i5-10210U、Visual C++ 2008)

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

solu.h 非負整数解の最小完全ハッシュ関数とその逆変換のヘッダファイル

solu.c 非負整数解の最小完全ハッシュ関数とその逆変換のプログラム

speed.c 最小完全ハッシュ関数とその逆変換の性能測定共通プログラム

/* speed-s.c 非負整数解の最小完全ハッシュ関数とその逆変換の性能測定プログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #include "speed.c" #include "solu.c" #define SN 37 #define SR 7 INDEX Source[SIZE],Sum; unsigned char Results[SIZE][SR]; int main(void) { INDEX sz=InitSolu(SN,SR); long clo,k; int i; if (sz==0) { printf("Error InitSolu(SN=%d,SR=%d) %s\n",SN,SR,SoluErrMsg); return 1; } for (i=0;i<SIZE;i++) Source[i]=(INDEX)(NextRand32()%sz); printf("InitSolu(%d,%d)=%.0f\n",SN,SR,(double)sz); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) NumToSolu(Results[i],Source[i]); printf(ITER_STR "NumToSolu() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC) ); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) Sum+=SoluToNum(Results[i]); printf(ITER_STR "SoluToNum() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC)); return 0; }

順列(permutation)

簡略版

例えぱ、0 1 2 3 のように 4 種類(n=4,n>0)の要素があるものとし、 これから 3 つ要素(r=3,r>0)を取り出して並べる場合を考える。
並べ方は、24 通りあって、辞書順での番号と並べ方を列挙すると、

 0:(0,1,2)   1:(0,1,3)   2:(0,2,1)   3:(0,2,3)   4:(0,3,1)   5:(0,3,2)
 6:(1,0,2)   7:(1,0,3)   8:(1,2,0)   9:(1,2,3)  10:(1,3,0)  11:(1,3,2)
12:(2,0,1)  13:(2,0,3)  14:(2,1,0)  15:(2,1,3)  16:(2,3,0)  17:(2,3,1)
18:(3,0,1)  19:(3,0,2)  20:(3,1,0)  21:(3,1,2)  22:(3,2,0)  23:(3,2,1)

となる。目的は、

以下に柔軟性のある正式版のプログラムを示す。

/* perm.h 順列の最小完全ハッシュ関数とその逆変換のヘッダファイル programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #if !defined(PermErrMsg) #include "code.h" extern code_t DefaultPerm[1]; extern INDEX InitPerm_r(code_t*const p,const int n,const int r, const tbl_t t TBL_OPT); extern INDEX PermToNum_r(const code_t*const p,const unsigned char*const vec); extern void NumToPerm_r (const code_t*const p,unsigned char*const vec,INDEX num); #define PermErrMsg (DefaultPerm->errmsg) #define PermErrCode (DefaultPerm->errcode) #define PermBytes (DefaultPerm->bytes) #define PermTbl (DefaultPerm->tbl) #define PermSize (DefaultPerm->size) #define InitPerm(n,r) InitPerm_r(DefaultPerm,n,r,TBL_STATIC) #define PermToNum(vec) PermToNum_r(DefaultPerm,vec) #define NumToPerm(vec,num) NumToPerm_r(DefaultPerm,vec,num) #endif

/* perm.c 順列の最小完全ハッシュ関数とその逆変換のプログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include "perm.h" code_t DefaultPerm[1]; INDEX InitPerm_r(code_t*const p,const int n,const int r,const tbl_t t) { int i,j; INDEX*a[MAX_PERM_R],*b,u,v; #ifdef __cplusplus if (p->type==CT_PERM&&p->size&&n==p->n&&r==p->r) return p->size; FreeCode(p); #else if (t==TBL_STATIC) { if (p->type==CT_PERM&&p->size&&n==p->n&&r==p->r) return p->size; FreeCode(p); } else p->ptr=0; #endif p->n=n; p->r=r; p->tbl=t; p->size=0; p->type=CT_PERM; p->errcode=CEC_PARAMETER; if (t!=TBL_STATIC&&t!=TBL_STACK) { p->errmsg="t!=TBL_STATIC:8 && t!=TBL_STACK:9"; return 0; } if (r<=0) { p->errmsg="r <= 0"; return 0; } if (n<=0) { p->errmsg="n <= 0"; return 0; } if (r>n) { p->errmsg="r > n"; return 0; } if (r>MAX_PERM_R) { p->errmsg="r > MAX_PERM_R"; return 0; } if (n>MAX_PERM_N) { p->errmsg="n > MAX_PERM_N"; return 0; } p->errcode=CEC_MEMORY; p->errmsg="memory error"; #if defined(__cplusplus) try { p->ptr=new INDEX[(n+n-r+1)*r/2]; } catch(...) { p->ptr=0; } #else p->ptr=(INDEX*)malloc((n+n-r+1)*r/2*sizeof(INDEX)); #endif if (p->ptr==0) return 0; p->bytes=((n+n-r+1)*r/2)*(int)sizeof(INDEX); b=p->ptr; for (i=0;i<r;b+=n-i++) a[i]=b; for (i=r-1;i>=0;i--) { if (i==r-1) a[i][0]=1; else a[i][0]=a[i+1][n-i-2]; for (j=1;j<n-i;j++) a[i][j]=a[i][0]+a[i][j-1]; } p->errcode=CEC_OVERFLOW; p->errmsg="Overflow"; for (i=0;i<r;i++) for (j=1;j<n-i;j++) if (a[i][j]<=a[i][j-1]) { FreeCode(p); return 0; } u=a[0][n-1]; v=u-1; if (u-v!=1) { FreeCode(p); return 0; } p->errcode=CEC_SUCCESS; p->errmsg=0; return p->size=u; } INDEX PermToNum_r(const code_t*const p,const unsigned char*const vec) { int i,j,k,n=p->n,r=p->r; INDEX*a=p->ptr,u=0; for (i=0;i<r;a+=n-i++) { for (k=vec[i],j=0;j<i;j++) if (vec[j]<vec[i]) k--; if (k) u+=a[k-1]; } return u; } void NumToPerm_r(const code_t*const p,unsigned char*const vec,INDEX num) { int i,j,k,n=p->n,r=p->r; char f[MAX_PERM_N]; INDEX*a=p->ptr; for (j=0;j<MAX_PERM_N;j++) f[j]=0; for (i=0;i<r;a+=n-i++) { for (k=0;a[k]<=num;k++) ; if (k) num-=a[k-1]; for (j=0;k>=0;k--,j++) while (f[j]) j++; f[--j]=1; vec[i]=(unsigned char)j; } }

/* test-p.c 順列の最小完全ハッシュ関数とその逆変換 perm.c のテスト programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #include <string.h> #include "perm.c" #define SCR 23 /* 画面の行数 */ int main(void) { int i,j,err=0,n=4,r=3; unsigned*a,s,sz=InitPerm(n,r); unsigned char vec[MAX_PERM_R],prev[MAX_PERM_R]; if (sz==0) { printf("Error InitPerm(n=%d,r=%d) %s\n",n,r,PermErrMsg); return 1; } for (s=0;s<sz;s++) { NumToPerm(vec,s); printf("%4u -> (%u", s,vec[0]); for (i=1;i<r;i++) printf(",%u",vec[i]); printf(") ->%4u\n", PermToNum(vec)); } printf(" HIT [ENTER] KEY > "); fgetc(stdin); printf("Permutation(n,r):checking ...\n "); for (r=1;r<=8;r++) printf(" r=%2d",r); printf("\n"); for (n=1;n<=8;n++) { printf("n=%2d",n); for (r=1;r<=n;r++) { sz=InitPerm(n,r); if (sz==0) { err++; continue; } printf("%7u",sz); for (s=0;s<sz;s++) { NumToPerm(vec,s); /* 辞書順で前の結果より大きいかどうかのテスト */ if (s>=1&&memcmp(prev,vec,r)>=0) err++; memcpy(prev,vec,r); /* 逆変換で元に戻るかのテスト */ if (PermToNum(vec)!=s) err++; } } printf("\n"); } printf("ErrorCount=%d >",err); fgetc(stdin); for (n=1;n<=7;n++) { for (r=1;r<=n;r++) { sz=InitPerm(n,r); if (sz==0) continue; for (i=0;i<10;i++) printf("\n"); printf(" InitPerm(n,r)=(%d,%d) size=%u\n",n,r,sz); a=DefaultPerm->ptr; for (i=0;i<r;a+=n-i,i++) { for (j=0;j<n-i;j++) printf("%5u",a[j]); printf("\n"); } if ((int)sz>SCR-r) sz=(unsigned)(SCR-r); for (s=0;s<sz;s++) { NumToPerm(vec,s); printf(" num=%-2u : ",s); if (r) { printf("vec[]={%u",vec[0]); for (j=1;j<r;j++) printf(",%u",vec[j]); printf("}\n"); } else printf("No Change\n"); } for (i=0;i<SCR-r-(int)sz;i++) printf("\n"); printf(" HIT [ENTER] KEY > "); fgetc(stdin); } } return 0; }

結果の最初は以下のようになる。

   0 -> (0,1,2) ->   0
   1 -> (0,1,3) ->   1
   2 -> (0,2,1) ->   2
   3 -> (0,2,3) ->   3
   4 -> (0,3,1) ->   4
   5 -> (0,3,2) ->   5
   6 -> (1,0,2) ->   6
   7 -> (1,0,3) ->   7
   8 -> (1,2,0) ->   8
   9 -> (1,2,3) ->   9
  10 -> (1,3,0) ->  10
  11 -> (1,3,2) ->  11
  12 -> (2,0,1) ->  12
  13 -> (2,0,3) ->  13
  14 -> (2,1,0) ->  14
  15 -> (2,1,3) ->  15
  16 -> (2,3,0) ->  16
  17 -> (2,3,1) ->  17
  18 -> (3,0,1) ->  18
  19 -> (3,0,2) ->  19
  20 -> (3,1,0) ->  20
  21 -> (3,1,2) ->  21
  22 -> (3,2,0) ->  22
  23 -> (3,2,1) ->  23

InitPerm(n,r) は2つの引数をともなう(n=4,r=3)。
InitPerm(n,r) は入力された n と r が正しいかどうか検査する。
n と r が正しくない場合、例えば、(n=3,r=4) ならエラーとなり０を返す。

さらに、順列の計算のときに、n と r が大きすぎて、 unsigned の範囲を超えオーバーフローを起こしたときもエラーとなり０を返す。
０を返した場合、整数 PermErrCode と文字列 PermErrMsg に原因が示される。

n と r が正しい場合、InitPerm(n,r) は順列が何通りあるかを返す。
例えば、InitPerm(4,3)の場合は 24 を返す。
InitPerm(n,r)は、また、PermToNum(vec), NumToPerm(vec,num) を高速に計算するのに必要な内部テーブルを設定する。

NumToPerm(vec,num) は、unsigned num で与えられた辞書順での番号から、 unsigned char vec[] へ順列を展開する。
num は、0 以上 InitPerm(n,r) 未満である。

PermToNum(vec) は、unsigned char vec[] で与えられた順列から 0 以上 InitPerm(n,r) 未満の辞書順での番号を unsigned で返す。

順列は他の組合せ等とは異なる表の使い方をしているので遅くなる。
この順列のプログラムは速度よりも使いやすさを優先している。

性能は、例えば speed-c.c より少し小さい規模(n=16,r=6)の場合、 NumToPerm( ) の一億回の実行で 18.698 秒。
PermToNum( ) の一億回の実行で 5.202 秒。
(Core i5-10210U、Visual C++ 2008)

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

perm.h 順列の最小完全ハッシュ関数とその逆変換のヘッダファイル

perm.c 順列の最小完全ハッシュ関数とその逆変換のプログラム

speed.c 最小完全ハッシュ関数とその逆変換の性能測定共通プログラム

/* speed-p.c 順列の最小完全ハッシュ関数とその逆変換の性能測定プログラム programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #include "speed.c" #include "perm.c" #define N 16 #define R 6 INDEX Source[SIZE],Sum; unsigned char Results[SIZE][R]; int main(void) { INDEX sz=InitPerm(N,R); long clo,k; int i; if (sz==0) { printf("Error InitPerm(N=%d,R=%d) %s\n",N,R,PermErrMsg); return 1; } for (i=0;i<SIZE;i++) Source[i]=(INDEX)(NextRand32()%sz); printf("InitPerm(%d,%d)=%.0f\n",N,R,(double)sz); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) NumToPerm(Results[i],Source[i]); printf(ITER_STR "NumToPerm() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC) ); clo=Tick(); for (k=0;k<ITER_NUM;k++) for (i=0;i<SIZE;i++) Sum+=PermToNum(Results[i]); printf(ITER_STR "PermToNum() execution times is %.3f sec.\n", (Tick()-clo)*(1.0/TICK_PER_SEC)); return 0; }

INDEX を変更して大きな問題を解く

型 INDEX は既定で unsigned に定義されているが、 これを変更することで組合せの数がより大きな問題を扱うことができる。
例えば

#define INDEX double

としたり

#define INDEX unsigned __int64

とする。

以下の例では double にすることで１００個から１３個を取り出す ランダムな組合せを２０組み生成する。
double を unsigned __int64 にすれば、より大きな組合せを生成できるが、 __int64 は１６ビットコンパイラには対応していない。

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

comb.h いわゆる組合せの最小完全ハッシュ関数とその逆変換のヘッダファイル

comb.c いわゆる組合せの最小完全ハッシュ関数とその逆変換のプログラム

/* index.c INDEX を変更して大きな問題を解く programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #define INDEX double #include "comb.c" #define CN 100 #define R 13 unsigned long NextRand32(void) { static unsigned long y=2463534242UL; y^=y<<13; y^=y>>17; return(y^=y<<5)&0xffffffffUL; } double NextUnif(void) { long a=(long)(NextRand32()>>5); /* 'a' has 27 random bits */ long b=(long)(NextRand32()>>6); /* 'b' has 26 random bits */ double c=a*67108864.0+b; /* 'c' has 53 random bits */ return c*(1.0/9007199254740992.0); } int main(void) { INDEX s,sz=InitComb(CN,R); int i,k; unsigned char vec[R]; if (sz==0) { printf("Error InitComb(cn=%d,r=%d) %s\n",CN,R,CombErrMsg); return 1; } printf("sz=%17.0f heap_bytes=%d\n",(double)sz,CombBytes); for (k=0;k<20;k++) { s=(INDEX)(sz*NextUnif()); printf("%2d=%17.0f:",k+1,(double)s); NumToComb(vec,s); for (i=0;i<R;i++) printf("%2u ",vec[i]); printf("\n"); } return 0; }

結果は以下のようになる。

sz= 7110542499799200 heap_bytes=18304
 1= 1197745205807305: 1  5  6 29 32 33 51 68 69 78 79 80 98 
 2= 3417299462603654: 4 12 13 19 35 40 41 44 59 63 65 77 93 
 3= 5847914623385354:11 19 31 33 52 55 64 67 68 69 85 94 96 
 4= 2236048815928662: 2 11 21 30 40 44 49 54 55 62 66 85 88 
 5= 1236463990822524: 1  5 14 21 27 28 48 50 53 84 86 93 94 
 6= 1914395770592783: 2  5  7 13 17 20 22 31 49 51 66 69 88 
 7= 4781951286116007: 7 17 18 24 47 48 55 61 66 76 80 81 94 
 8= 3244335163837346: 4  7 18 20 28 35 37 46 54 66 68 72 84 
 9= 2362562099782447: 2 17 26 27 32 34 44 64 67 73 88 89 92 
10= 6138018370218479:13 16 24 29 41 48 49 54 58 64 69 90 94 
11= 7003931231035093:25 38 42 45 46 66 67 68 69 70 76 89 98 
12= 1919750768853946: 2  5  8 11 14 30 35 36 53 66 79 80 97 
13= 4993788983269408: 8 12 14 25 31 46 49 51 63 68 76 83 85 
14= 4059845603381931: 5 22 31 33 41 55 56 59 71 76 84 86 89 
15=  225189026934321: 0  3  5 10 15 24 37 69 71 88 89 91 98 
16= 2552277604930980: 3  5  9 15 34 36 54 58 64 77 80 84 99 
17= 2263450251109646: 2 12 21 23 48 55 73 77 84 87 88 92 96 
18= 3178090434535520: 4  6 13 19 36 40 60 64 66 78 86 87 94 
19=  432196378388683: 0  5 17 26 44 45 49 51 54 61 65 80 96 
20= 4766446631063488: 7 16 17 29 30 37 44 45 46 74 76 86 91 

マルチスレッドで使用する場合の注意

NumTo????() と ????ToNum() はテーブルを読むだけで書き込むことはしない。
従って、code_t を使わずに、複数のスレッドでテーブルを共用し、Init????() を メインスレッドで最初に使うだけの場合は、マルチスレッドで安全に使うことができる。
Init????() をマルチスレッドから呼び出す必要がある場合は、 代わりに次の章の Init????_r( ) を使う。

テーブルを宣言して使用する場合

今まで挙げた例では、既定のテーブルを使っていた。
code_t 型のテーブルを宣言して関数名に _r を加えたバージョンを使えば、 複数のテーブルを同時に使うことができる。
またマルチスレッドなどで Init????_r() を安全に使うことができる。

下の例は、上ののプログラムを _r バージョンを使うように 変更したものである。
エラーメッセージを見る場合は、CombErrMsg ではなく、tbl->errmsg を見ること。
InitComb_r(tbl,cn,r,t) の t は構造体 tbl がスタックにある場合は TBL_STACK を 指定する。その以外の場合、つまり tbl がグローバル宣言されていたり、 static 宣言されている場合は TBL_STATIC を指定する。
Ｃ＋＋言語の場合 t は省略できる。
Ｃ言語の InitComb_r(tbl,cn,r,t) で t が TBL_STACK の場合は tbl に確保されたしたメモリを使用後に FreeCode(tbl) で解放する必要がある。
Ｃ言語でも t が TBL_STATIC の場合では FreeCode(tbl)はあっても無くてもよい。
Ｃ＋＋言語では TBL_STATIC でも TBL_STACK のどちらでも FreeCode(tbl)はあっても無くてもよい。

tbl.c の結果は index.c と同じである。

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

comb.h いわゆる組合せの最小完全ハッシュ関数とその逆変換のヘッダファイル

comb.c いわゆる組合せの最小完全ハッシュ関数とその逆変換のプログラム

/* tbl.c テーブルを宣言して使用する場合 programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #include <stdio.h> #define INDEX double #include "comb.c" #define CN 100 #define R 13 unsigned long NextRand32(void) { static unsigned long y=2463534242UL; y^=y<<13; y^=y>>17; return(y^=y<<5)&0xffffffffUL; } double NextUnif(void) { long a=(long)(NextRand32()>>5); /* 'a' has 27 random bits */ long b=(long)(NextRand32()>>6); /* 'b' has 26 random bits */ double c=a*67108864.0+b; /* 'c' has 53 random bits */ return c*(1.0/9007199254740992.0); } int main(void) { code_t tbl[1]; INDEX s,sz=InitComb_r(tbl,CN,R,TBL_STACK); int i,k; unsigned char vec[R]; if (sz==0) { printf("Error InitComb_r(tbl,cn=%d,r=%d,t=%d) %s\n", CN,R,tbl->tbl,tbl->errmsg); return 1; } printf("sz=%17.0f heap_bytes=%d\n",(double)sz,tbl->bytes); for (k=0;k<20;k++) { s=(INDEX)(sz*NextUnif()); printf("%2d=%17.0f:",k+1,(double)s); NumToComb_r(tbl,vec,s); for (i=0;i<R;i++) printf("%2u ",vec[i]); printf("\n"); } FreeCode(tbl); return 0; }

r に対する最大の n の値と組合せの総数

code.h 組合せ等の最小完全ハッシュ関数と逆変換の共通ヘッダファイル

repe.h 重複組合せの最小完全ハッシュ関数とその逆変換のヘッダファイル

perm.h 順列の最小完全ハッシュ関数とその逆変換のヘッダファイル

repe.c 重複組合せの最小完全ハッシュ関数とその逆変換のプログラム

perm.c 順列の最小完全ハッシュ関数とその逆変換のプログラム

/* max.c rに対する最大のnの値と組合せの総数を求める programmed by Isaku WADA isaku@pb4.so-net.ne.jp */ #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #if !defined(INDEX) #define INDEX unsigned #endif #include "repe.c" #include "perm.c" #define TO_STR_BASE(X) #X #define TO_STR(X) TO_STR_BASE(X) #define INDEX_STR TO_STR(INDEX) /* const char*i2a(INDEX value) INDEX 型を１０進文字列に変換する。 float 最小表現不可能正整数 16,777,217 i2a() の最大表示可能整数 99,999,993,536,462,043,136 double 最小表現不可能正整数 9,007,199,254,740,993 i2a() の最大表示可能整数 99,999,999,999,999,983,616 long double ( Visual C++ では long double は double と同一 ) 最小表現不可能正整数 18,446,744,073,709,551,617 i2a() の最大表示可能整数 99,999,999,999,999,999,992 char -128 ～ 127 unsigned char 0 ～ 255 short -32,768 ～ 32,767 unsigned short 0 ～ 65,535 int ( 16ビットコンパイラでは long ) -2,147,483,648 ～ 2,147,483,647 unsigned ( 16ビットコンパイラでは unsigned long ) 0 ～ 4,294,967,295 __int64 ( long long ) -9,223,372,036,854,775,808 ～ 9,223,372,036,854,775,807 unsigned __int64 ( unsigned long long ) 0 ～ 18,446,744,073,709,551,615 */ const char*i2a(INDEX value) { enum { MX=20, SW=8 }; static int mx,ok,sw; static INDEX zero,tbl[MX]; static char buf[SW][MX+2]; char*ret=buf[sw++%SW]+1,*p=ret; int i,g=0; if (mx==0) { INDEX x,x2,x4,x8,x10=0; for (tbl[0]=x=1,mx=1;mx<=MX;mx++) { if ((x2=x+x)<x) break; if ((x4=x2+x2)<x2) break; if ((x8=x4+x4)<x4) break; if ((x10=x8+x2)<x8) break; x=x10; if (mx<MX) tbl[mx]=x; } x=x10-1; if (x10-x!=1||mx<=MX) ok=1; if (mx==MX+1) mx=MX; /* printf("ok=%d mx=%d tbl[mx-1]=%.0f\n",ok,mx,(double)tbl[mx-1]); */ } if (value<zero) { *--ret='-'; value*=(INDEX)(-1); if (value<zero) { g=1; value--; } } if (ok==0||value/tbl[mx-1]>=10) return"(error)"; for (i=0;i<mx;i++) if (value<tbl[i]) break; if (i==0) return"0"; while (--i>=0) { INDEX t=tbl[i]; int v=(int)(value/t); *p++=(char)('0'+v); value-=(INDEX)(t*v); if (g) { g=0; value++; } } *p=0; return ret; } int main(void) { int n,m=0,r,x=0,bytes=0,max_bytes=0,bits; INDEX sz=0,tz=0; FILE*fp; char fn[100]; code_t tbl1[1]; INDEX minus_one=(INDEX)-1; if (strcmp(INDEX_STR,"long double")==0) bits=(sizeof(INDEX)==8?53:80); else if (strcmp(INDEX_STR,"double")==0) bits=53; else if (strcmp(INDEX_STR,"float")==0) bits=24; else bits=(int)sizeof(INDEX)*8-(minus_one<1); sprintf(fn,"max%d-%d.txt",(int)sizeof(size_t)*8,bits); if ((fp=fopen(fn,"w"))==0) { printf("'%s' cannot open\n",fn); return 1; } #if defined(__cplusplus) printf("C++ %d\n",(int)sizeof(size_t)*8); #else printf("C %d\n",(int)sizeof(size_t)*8); #endif printf("#define INDEX " INDEX_STR "\n"); fprintf(fp,"#define INDEX " INDEX_STR "\n"); for (r=0;r<=MAX_CODE_R;r++) for (n=1;n<=MAX_CODE_N+1;n++,tz=sz) if ((sz=InitRepe_r(tbl1,n,r,TBL_STACK))==0) { code_t tbl2[1]; if (tbl1->errcode==CEC_OVERFLOW&&n<=x) if (InitRepe_r(tbl2,m,r+1,TBL_STACK)) { FreeCode(tbl2); break; } fprintf(fp,"InitComb(%3d,%3d) InitRepe(%3d,%3d) ",m+r-1,r,m,r); fprintf(fp,"InitSolu(%3d,%3d) = %s\n",m-1,r+1,i2a(tz)); if (bytes>max_bytes) max_bytes=bytes; x=n; break; } else { bytes=tbl1->bytes; m=n; FreeCode(tbl1); } printf("repe max_heap_bytes=%d\n",max_bytes); fprintf(fp,"repe max_heap_bytes=%d\n",max_bytes); max_bytes=0; for (r=1;r<=MAX_PERM_R&&(tz=InitPerm_r(tbl1,r,r,TBL_STACK))!=0;r++) { for (n=r;n<=MAX_PERM_N+1;n++,tz=sz) if (tz) { code_t tbl2[1]; if ((sz=InitPerm_r(tbl2,n,r,TBL_STACK))==0) { fprintf(fp,"InitPerm(%3d,%2d) = %s\n",(n-1),r,i2a(tz)); if (bytes>max_bytes) max_bytes=bytes; break; } else { bytes=tbl2->bytes; FreeCode(tbl2); } } FreeCode(tbl1); } printf("perm max_heap_bytes=%d\n",max_bytes); fprintf(fp,"perm max_heap_bytes=%d\n",max_bytes); fclose(fp); printf("Wrote '%s'.\n",fn); return 0; }

INDEX が unsigned short の場合

#define INDEX unsigned short
InitComb(245,  0) InitRepe(246,  0) InitSolu(245,  1) = 1
InitComb(246,  1) InitRepe(246,  1) InitSolu(245,  2) = 246
InitComb(247,  2) InitRepe(246,  2) InitSolu(245,  3) = 30381
InitComb( 74,  3) InitRepe( 72,  3) InitSolu( 71,  4) = 64824
InitComb( 36,  4) InitRepe( 33,  4) InitSolu( 32,  5) = 58905
InitComb( 25,  5) InitRepe( 21,  5) InitSolu( 20,  6) = 53130
InitComb( 21,  6) InitRepe( 16,  6) InitSolu( 15,  7) = 54264
InitComb( 19,  7) InitRepe( 13,  7) InitSolu( 12,  8) = 50388
InitComb( 18,  8) InitRepe( 11,  8) InitSolu( 10,  9) = 43758
InitComb( 18,  9) InitRepe( 10,  9) InitSolu(  9, 10) = 48620
InitComb( 18, 10) InitRepe(  9, 10) InitSolu(  8, 11) = 43758
InitComb( 19, 12) InitRepe(  8, 12) InitSolu(  7, 13) = 50388
InitComb( 21, 15) InitRepe(  7, 15) InitSolu(  6, 16) = 54264
InitComb( 25, 20) InitRepe(  6, 20) InitSolu(  5, 21) = 53130
InitComb( 36, 32) InitRepe(  5, 32) InitSolu(  4, 33) = 58905
InitComb( 74, 71) InitRepe(  4, 71) InitSolu(  3, 72) = 64824
InitComb(102,100) InitRepe(  3,100) InitSolu(  2,101) = 5151
repe max_heap_bytes=1968
InitPerm(256, 1) = 256
InitPerm(256, 2) = 65280
InitPerm( 41, 3) = 63960
InitPerm( 17, 4) = 57120
InitPerm( 11, 5) = 55440
InitPerm(  9, 6) = 60480
InitPerm(  8, 7) = 40320
InitPerm(  8, 8) = 40320
perm max_heap_bytes=1024

INDEX が 32 ビット unsigned 場合

#define INDEX unsigned
InitComb(245,  0) InitRepe(246,  0) InitSolu(245,  1) = 1
InitComb(246,  1) InitRepe(246,  1) InitSolu(245,  2) = 246
InitComb(247,  2) InitRepe(246,  2) InitSolu(245,  3) = 30381
InitComb(248,  3) InitRepe(246,  3) InitSolu(245,  4) = 2511496
InitComb(249,  4) InitRepe(246,  4) InitSolu(245,  5) = 156340626
InitComb(222,  5) InitRepe(218,  5) InitSolu(217,  6) = 4294249674
InitComb(123,  6) InitRepe(118,  6) InitSolu(117,  7) = 4249404082
InitComb( 83,  7) InitRepe( 77,  7) InitSolu( 76,  8) = 4151918628
InitComb( 63,  8) InitRepe( 56,  8) InitSolu( 55,  9) = 3872894697
InitComb( 52,  9) InitRepe( 44,  9) InitSolu( 43, 10) = 3679075400
InitComb( 46, 10) InitRepe( 37, 10) InitSolu( 36, 11) = 4076350421
InitComb( 42, 11) InitRepe( 32, 11) InitSolu( 31, 12) = 4280561376
InitComb( 39, 12) InitRepe( 28, 12) InitSolu( 27, 13) = 3910797436
InitComb( 37, 13) InitRepe( 25, 13) InitSolu( 24, 14) = 3562467300
InitComb( 36, 14) InitRepe( 23, 14) InitSolu( 22, 15) = 3796297200
InitComb( 35, 15) InitRepe( 21, 15) InitSolu( 20, 16) = 3247943160
InitComb( 35, 16) InitRepe( 20, 16) InitSolu( 19, 17) = 4059928950
InitComb( 34, 17) InitRepe( 18, 17) InitSolu( 17, 18) = 2333606220
InitComb( 35, 19) InitRepe( 17, 19) InitSolu( 16, 20) = 4059928950
InitComb( 35, 20) InitRepe( 16, 20) InitSolu( 15, 21) = 3247943160
InitComb( 36, 22) InitRepe( 15, 22) InitSolu( 14, 23) = 3796297200
InitComb( 37, 24) InitRepe( 14, 24) InitSolu( 13, 25) = 3562467300
InitComb( 39, 27) InitRepe( 13, 27) InitSolu( 12, 28) = 3910797436
InitComb( 42, 31) InitRepe( 12, 31) InitSolu( 11, 32) = 4280561376
InitComb( 46, 36) InitRepe( 11, 36) InitSolu( 10, 37) = 4076350421
InitComb( 52, 43) InitRepe( 10, 43) InitSolu(  9, 44) = 3679075400
InitComb( 63, 55) InitRepe(  9, 55) InitSolu(  8, 56) = 3872894697
InitComb( 83, 76) InitRepe(  8, 76) InitSolu(  7, 77) = 4151918628
InitComb(106,100) InitRepe(  7,100) InitSolu(  6,101) = 1705904746
repe max_heap_bytes=8720
InitPerm(256, 1) = 256
InitPerm(256, 2) = 65280
InitPerm(256, 3) = 16581120
InitPerm(256, 4) = 4195023360
InitPerm( 86, 5) = 4179156240
InitPerm( 42, 6) = 3776965920
InitPerm( 26, 7) = 3315312000
InitPerm( 19, 8) = 3047466240
InitPerm( 16, 9) = 4151347200
InitPerm( 14,10) = 3632428800
InitPerm( 13,11) = 3113510400
InitPerm( 12,12) = 479001600
perm max_heap_bytes=4096

INDEX が double の場合

#define INDEX double
InitComb(245,  0) InitRepe(246,  0) InitSolu(245,  1) = 1
InitComb(246,  1) InitRepe(246,  1) InitSolu(245,  2) = 246
InitComb(247,  2) InitRepe(246,  2) InitSolu(245,  3) = 30381
InitComb(248,  3) InitRepe(246,  3) InitSolu(245,  4) = 2511496
InitComb(249,  4) InitRepe(246,  4) InitSolu(245,  5) = 156340626
InitComb(250,  5) InitRepe(246,  5) InitSolu(245,  6) = 7817031300
InitComb(251,  6) InitRepe(246,  6) InitSolu(245,  7) = 327012476050
InitComb(252,  7) InitRepe(246,  7) InitSolu(245,  8) = 11772449137800
InitComb(253,  8) InitRepe(246,  8) InitSolu(245,  9) = 372303703982925
InitComb(249,  9) InitRepe(241,  9) InitSolu(240, 10) = 8760212643481299
InitComb(182, 10) InitRepe(173, 10) InitSolu(172, 11) = 8543814344395330
InitComb(143, 11) InitRepe(133, 11) InitSolu(132, 12) = 8634941152058949
InitComb(118, 12) InitRepe(107, 12) InitSolu(106, 13) = 8531742652084314
InitComb(101, 13) InitRepe( 89, 13) InitSolu( 88, 14) = 8160963550905900
InitComb( 89, 14) InitRepe( 76, 14) InitSolu( 75, 15) = 7632612327410136
InitComb( 81, 15) InitRepe( 67, 15) InitSolu( 66, 16) = 8144022047817960
InitComb( 75, 16) InitRepe( 60, 16) InitSolu( 59, 17) = 8550047575185300
InitComb( 70, 17) InitRepe( 54, 17) InitSolu( 53, 18) = 7877932561061640
InitComb( 66, 18) InitRepe( 49, 18) InitSolu( 48, 19) = 6848956078664700
InitComb( 64, 19) InitRepe( 46, 19) InitSolu( 45, 20) = 8719878125622720
InitComb( 61, 20) InitRepe( 42, 20) InitSolu( 41, 21) = 6236646703759395
InitComb( 60, 21) InitRepe( 40, 21) InitSolu( 39, 22) = 7984465725343800
InitComb( 59, 22) InitRepe( 38, 22) InitSolu( 37, 23) = 8964377427999630
InitComb( 58, 23) InitRepe( 36, 23) InitSolu( 35, 24) = 8799226775309880
InitComb( 57, 24) InitRepe( 34, 24) InitSolu( 33, 25) = 7522327487513475
InitComb( 56, 25) InitRepe( 32, 25) InitSolu( 31, 26) = 5574440580220512
InitComb( 56, 26) InitRepe( 31, 26) InitSolu( 30, 27) = 6646448384109072
InitComb( 56, 27) InitRepe( 30, 27) InitSolu( 29, 28) = 7384942649010080
InitComb( 56, 28) InitRepe( 29, 28) InitSolu( 28, 29) = 7648690600760440
InitComb( 56, 29) InitRepe( 28, 29) InitSolu( 27, 30) = 7384942649010080
InitComb( 56, 30) InitRepe( 27, 30) InitSolu( 26, 31) = 6646448384109072
InitComb( 56, 31) InitRepe( 26, 31) InitSolu( 25, 32) = 5574440580220512
InitComb( 57, 33) InitRepe( 25, 33) InitSolu( 24, 34) = 7522327487513475
InitComb( 58, 35) InitRepe( 24, 35) InitSolu( 23, 36) = 8799226775309880
InitComb( 59, 37) InitRepe( 23, 37) InitSolu( 22, 38) = 8964377427999630
InitComb( 60, 39) InitRepe( 22, 39) InitSolu( 21, 40) = 7984465725343800
InitComb( 61, 41) InitRepe( 21, 41) InitSolu( 20, 42) = 6236646703759395
InitComb( 64, 45) InitRepe( 20, 45) InitSolu( 19, 46) = 8719878125622720
InitComb( 66, 48) InitRepe( 19, 48) InitSolu( 18, 49) = 6848956078664700
InitComb( 70, 53) InitRepe( 18, 53) InitSolu( 17, 54) = 7877932561061640
InitComb( 75, 59) InitRepe( 17, 59) InitSolu( 16, 60) = 8550047575185300
InitComb( 81, 66) InitRepe( 16, 66) InitSolu( 15, 67) = 8144022047817960
InitComb( 89, 75) InitRepe( 15, 75) InitSolu( 14, 76) = 7632612327410136
InitComb(101, 88) InitRepe( 14, 88) InitSolu( 13, 89) = 8160963550905900
InitComb(112,100) InitRepe( 13,100) InitSolu( 12,101) = 4416904685676756
repe max_heap_bytes=34704
InitPerm(256, 1) = 256
InitPerm(256, 2) = 65280
InitPerm(256, 3) = 16581120
InitPerm(256, 4) = 4195023360
InitPerm(256, 5) = 1057145886720
InitPerm(256, 6) = 265343617566720
InitPerm(193, 7) = 8935251187484160
InitPerm(102, 8) = 8841977153856000
InitPerm( 63, 9) = 8588531280067200
InitPerm( 44,10) = 9003984596006400
InitPerm( 33,11) = 7725366544896000
InitPerm( 27,12) = 8326896754176000
InitPerm( 23,13) = 7124122778572800
InitPerm( 20,14) = 3379030566912000
InitPerm( 19,15) = 5068545850368000
InitPerm( 18,16) = 3201186852864000
InitPerm( 18,17) = 6402373705728000
InitPerm( 18,18) = 6402373705728000
perm max_heap_bytes=12288

INDEX が unsigned __int64 の場合

#define INDEX unsigned __int64
InitComb(245,  0) InitRepe(246,  0) InitSolu(245,  1) = 1
InitComb(246,  1) InitRepe(246,  1) InitSolu(245,  2) = 246
InitComb(247,  2) InitRepe(246,  2) InitSolu(245,  3) = 30381
InitComb(248,  3) InitRepe(246,  3) InitSolu(245,  4) = 2511496
InitComb(249,  4) InitRepe(246,  4) InitSolu(245,  5) = 156340626
InitComb(250,  5) InitRepe(246,  5) InitSolu(245,  6) = 7817031300
InitComb(251,  6) InitRepe(246,  6) InitSolu(245,  7) = 327012476050
InitComb(252,  7) InitRepe(246,  7) InitSolu(245,  8) = 11772449137800
InitComb(253,  8) InitRepe(246,  8) InitSolu(245,  9) = 372303703982925
InitComb(254,  9) InitRepe(246,  9) InitSolu(245, 10) = 10507237867962550
InitComb(255, 10) InitRepe(246, 10) InitSolu(245, 11) = 267934565633045025
InitComb(256, 11) InitRepe(246, 11) InitSolu(245, 12) = 6235568072914502400
InitComb(218, 12) InitRepe(207, 12) InitSolu(206, 13) = 17671866771244267764
InitComb(177, 13) InitRepe(165, 13) InitSolu(164, 14) = 17112638902445186100
InitComb(150, 14) InitRepe(137, 14) InitSolu(136, 15) = 17910906207136060650
InitComb(130, 15) InitRepe(116, 15) InitSolu(115, 16) = 16906502128836777600
InitComb(116, 16) InitRepe(101, 16) InitSolu(100, 17) = 17376988841260199871
InitComb(105, 17) InitRepe( 89, 17) InitSolu( 88, 18) = 16391295291994500150
InitComb( 97, 18) InitRepe( 80, 18) InitSolu( 79, 19) = 16794366584493727440
InitComb( 91, 19) InitRepe( 73, 19) InitSolu( 72, 20) = 18150420051920130975
InitComb( 86, 20) InitRepe( 67, 20) InitSolu( 66, 21) = 18293741700978245355
InitComb( 82, 21) InitRepe( 62, 21) InitSolu( 61, 22) = 18330655594514646240
InitComb( 78, 22) InitRepe( 57, 22) InitSolu( 56, 23) = 14170178259145435020
InitComb( 76, 23) InitRepe( 54, 23) InitSolu( 53, 24) = 17061084191613232800
InitComb( 74, 24) InitRepe( 51, 24) InitSolu( 50, 25) = 17529515713716297876
InitComb( 72, 25) InitRepe( 48, 25) InitSolu( 47, 26) = 15264502391210933952
InitComb( 71, 26) InitRepe( 46, 26) InitSolu( 45, 27) = 17629195603524593592
InitComb( 70, 27) InitRepe( 44, 27) InitSolu( 43, 28) = 18208558839321176480
InitComb( 69, 28) InitRepe( 42, 28) InitSolu( 41, 29) = 16777886359088798328
InitComb( 68, 29) InitRepe( 40, 29) InitSolu( 39, 30) = 13750991318793417920
InitComb( 68, 30) InitRepe( 39, 30) InitSolu( 38, 31) = 17876288714431443296
InitComb( 67, 31) InitRepe( 37, 31) InitSolu( 36, 32) = 11923179284862717872
InitComb( 67, 32) InitRepe( 36, 32) InitSolu( 35, 33) = 13413576695470557606
InitComb( 67, 33) InitRepe( 35, 33) InitSolu( 34, 34) = 14226520737620288370
InitComb( 67, 34) InitRepe( 34, 34) InitSolu( 33, 35) = 14226520737620288370
InitComb( 67, 35) InitRepe( 33, 35) InitSolu( 32, 36) = 13413576695470557606
InitComb( 67, 36) InitRepe( 32, 36) InitSolu( 31, 37) = 11923179284862717872
InitComb( 68, 38) InitRepe( 31, 38) InitSolu( 30, 39) = 17876288714431443296
InitComb( 68, 39) InitRepe( 30, 39) InitSolu( 29, 40) = 13750991318793417920
InitComb( 69, 41) InitRepe( 29, 41) InitSolu( 28, 42) = 16777886359088798328
InitComb( 70, 43) InitRepe( 28, 43) InitSolu( 27, 44) = 18208558839321176480
InitComb( 71, 45) InitRepe( 27, 45) InitSolu( 26, 46) = 17629195603524593592
InitComb( 72, 47) InitRepe( 26, 47) InitSolu( 25, 48) = 15264502391210933952
InitComb( 74, 50) InitRepe( 25, 50) InitSolu( 24, 51) = 17529515713716297876
InitComb( 76, 53) InitRepe( 24, 53) InitSolu( 23, 54) = 17061084191613232800
InitComb( 78, 56) InitRepe( 23, 56) InitSolu( 22, 57) = 14170178259145435020
InitComb( 82, 61) InitRepe( 22, 61) InitSolu( 21, 62) = 18330655594514646240
InitComb( 86, 66) InitRepe( 21, 66) InitSolu( 20, 67) = 18293741700978245355
InitComb( 91, 72) InitRepe( 20, 72) InitSolu( 19, 73) = 18150420051920130975
InitComb( 97, 79) InitRepe( 19, 79) InitSolu( 18, 80) = 16794366584493727440
InitComb(105, 88) InitRepe( 18, 88) InitSolu( 17, 89) = 16391295291994500150
InitComb(116,100) InitRepe( 17,100) InitSolu( 16,101) = 17376988841260199871
repe max_heap_bytes=43296
InitPerm(256, 1) = 256
InitPerm(256, 2) = 65280
InitPerm(256, 3) = 16581120
InitPerm(256, 4) = 4195023360
InitPerm(256, 5) = 1057145886720
InitPerm(256, 6) = 265343617566720
InitPerm(256, 7) = 66335904391680000
InitPerm(256, 8) = 16517640193528320000
InitPerm(142, 9) = 18122888636548012800
InitPerm( 88,10) = 16379197879187404800
InitPerm( 61,11) = 16688980681121548800
InitPerm( 45,12) = 13776096431889792000
InitPerm( 36,13) = 14389334903623680000
InitPerm( 30,14) = 12677700308232960000
InitPerm( 26,15) = 10103301395066880000
InitPerm( 24,16) = 15388105201717248000
InitPerm( 22,17) = 9366672731480064000
InitPerm( 21,18) = 8515157028618240000
InitPerm( 20,19) = 2432902008176640000
InitPerm( 20,20) = 2432902008176640000
perm max_heap_bytes=16384