トップ

組合せに対応する整数への変換と逆変換

新しいバージョン

ソース・コード

2022年の変更 :

2009年の変更 :

このライブラリはＣ言語で書かれたフリーソフトウェアである。 このライブラリは、組合せの整数化と逆変換を高速に行なう。 このうち整数化のことを、最小完全ハッシュ関数ともいう。 使用メモリも少ない。 このライブラリは以下の組み合わせに対応している。

応用例

いわゆる組合せ

例えぱ、0 1 2 3 4 のように 5 種類(n=5,n>=0)の要素があるものと し、これから 3 つ要素(r=3,0<=r<=n)を取り出す場合を考える。取 り出し方は 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)を同じものと考える。目的は、

取り出し方に、何通りあるかを知る InitComb( )
各取り出し方に、番号をつける CombToNum( )
逆に番号から、取り出し方を求めるNumToComb( )

を行なうことである。この場合の簡単なプログラムを示す。

#include <stdio.h>
#include "zcode.c"
int main(void)
{
    unsigned i,s;  int vec[3];

    s=InitComb(5,3);
    for (i=0;i<s;i++) {
        printf(" %u -> ", i);
        NumToComb(vec,i);
        printf("(%d,%d,%d)",vec[0],vec[1],vec[2]);
        printf(" -> %u\n", CombToNum(vec));
    }
    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(5,3) は2つの引数をともなう(n=5,r=3)。 InitComb( ) はエラーが発生すると0を返す。 InitComb( ) は入力された n と r が正しいかどうか検査する。 n と r が正しくない場合、例えば、(n=5,r=6) ならエラーとなる。 このとき、グローバル変数 CodeErrorCode は CEC_PARAMETER となる。 また、テーブルを作成中にメモリが足りなくなくなると、エラーとなる。 このとき、CodeErrorCode は CEC_MEMORY となる。

さらに、組み合わせの計算のときに、n と r が大きすぎて、 unsigned の範囲を超えオーバーフローを起こしたときも、エラーになる。 このとき、CodeErrorCode は CEC_OVERFLOW となる。 n と r が正しい場合、InitComb( ) は組み合わせが何通りあるかを返す。 例えば、(5,3)の場合は 10 を返す。InitComb( )は、また、CombToNum( ) と NumToComb( ) を高速に計算するのに必要な内部テーブルを作成する。

NumToComb(vec,i) は、unsigned i で与えられた番号から、 int vec[3] へ取り出し方を展開する。i は、0 以上 10 未満で ある。

CombToNum(vec) は、int vec[3] で与えられた取り出し方から 0 以 上 10 未満の辞書順での番号を unsigned で返す。 マクロ NO_CODE_SORT を定義すれば高速になるが vec[3] はソートされている必要がある。

性能は、例えば、ロト６のような場合(n=43,r=6)、NumToComb( ) の 一億回の実行で 6.998 秒、 NO_CODE_SORT が定義された CombToNum( ) の一億回の実行で 0.625 秒、 NO_CODE_SORT が定義されない CombToNum( ) の一億回の実行で 1.390 秒となった。 また、このときのテーブルの大きさは 1872 バイトとなった。(Core i5-10210U、Visual C++ 2008) プログラムはこちら(speed.c)

comb.c : zcode.c を使わずに、できるだけ簡単に同じ出力を得るプログラム

分割組合せ

例えぱ、3 個の球(n=3,n>=0)があるものとし、これを 3 つの箱 (r=3,r>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)

となる。この場合の簡単なプログラムを示す。

#include <stdio.h>
#include "zcode.c"
int main(void)
{
    unsigned i,s;  int vec[3];

    s=InitPart(3,3);
    for (i=0;i<s;i++) {
        printf(" %u -> ", i);
        NumToPart(vec,i);
        printf("(%d,%d,%d)",vec[0],vec[1],vec[2]);
        printf(" -> %u\n", PartToNum(vec));
    }
    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

part.c : zcode.c を使わずに、できるだけ簡単に同じ出力を得るプログラム

重複組合せ

例えぱ、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)

となる。この場合の簡単なプログラムを示す。

#include <stdio.h>
#include "zcode.c"
int main(void)
{
    unsigned i,s;  int vec[3];

    s=InitRepe(3,3);
    for (i=0;i<s;i++) {
        printf(" %u -> ", i);
        NumToRepe(vec,i);
        printf("(%d,%d,%d)",vec[0],vec[1],vec[2]);
        printf(" -> %u\n", RepeToNum(vec));
    }
    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

RepeToNum(vec) は、マクロ NO_CODE_SORT を定義すれば高速になるが vec[3] はソートされている必要がある。

repe.c : zcode.c を使わずに、できるだけ簡単に同じ出力を得るプログラム

順列

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

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

となる。この場合の簡単なプログラムを示す。

#include <stdio.h>
#include "zcode.c"
int main(void)
{
    unsigned i,s;  int vec[2];

    s=InitPerm(4,2);
    for (i=0;i<s;i++) {
        printf(" %2u -> ", i);
        NumToPerm(vec,i);
        printf("(%d,%d)",vec[0],vec[1]);
        printf(" -> %2u\n", PermToNum(vec));
    }
    return 0;
}

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

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

perm.c : zcode.c を使わずに、できるだけ簡単に同じ出力を得るプログラム

複数のテーブルを使用する場合

今まで挙げた例では、単一の内部テーブルを使っていたが、 関数名に _r を加えたバージョンを使えば、 複数のテーブルを使うことができる。 マルチスレッドなどで安全に使うことができる。

下の例は、最初のプログラムを _r バージョンを使うように 変更したものである。 エラーコードを見る場合は、CodeErrorCode ではなく、 tbl->ErrorCode を見ること。

#include <stdio.h>
#include "zcode.c"

int main(void)
{
    unsigned i,s;  int vec[3]; code_t tbl[1];

    s=InitComb_r(tbl,5,3);
    for (i=0;i<s;i++) {
        printf(" %u -> ", i);
        NumToComb_r(tbl,vec,i);
        printf("(%d,%d,%d)",vec[0],vec[1],vec[2]);
        printf(" -> %u\n", CombToNum_r(tbl,vec));
    }
    return 0;
}

code_t はＣ言語の場合固定サイズの領域を取る。 従って、領域不足になる場合がある。 zcode.h の CODE_TABLE_SIZE を大きくしたり、 zcode.c をインクルードする前に、

#define CODE_TABLE_SIZE 32768

のように大きくすると解決する。 デフォルトの CODE_TABLE_SIZE は、10240 byte である。
(16ビットＣコンパイラの場合は 2048 byte である。)
Ｃ＋＋言語としてコンパイルした場合、メモリが足りなくなる可能性はほとんどない。 CODE_TABLE_SIZE は無視され、必要な領域が new を使って動的に確保される。

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

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

n と r が異なるものを同時に複数使う場合は code_t を使って、それ専用のテーブルを用意する必要がある。 複数のスレッドが頻繁に Init????_r() を呼び出す場合は、 極めて低い確率で MaxCodeTableSize が正しい値にならない可能性がある。

unsigned で扱える数よりも大きな問題を解く場合

組み合わせの数がオーバーフローを起こすような大きな問題を扱う場合、 zcode.h の INDEX の定義を double にしたり、__int64 にしたり、あるいは、 zcode.c をインクルードする前に、

#define INDEX double
にしたり、 
#define INDEX __int64

にすれば、unsigned で扱える数値より大きなものを扱える。

下の例では 100 種類から 10 個を選ぶ 17,10,309,456,440 通りの組合せを扱っている。

下の例で NextUnif( ) は 53 ビットの精度を持つので、 どの組み合わせもほぼ等しい確率で選ばれる。

#include <stdio.h>
#define INDEX double
#define CODE_TABLE_SIZE 15360
#include "zcode.c"

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) {
    static code_t tbl[1]; INDEX sz=InitComb_r(tbl,100,10); int i,j,r[10];

    if (tbl->ErrorCode==CEC_MEMORY)
        printf("テーブルの大きさが足りません\n");
    if (tbl->ErrorCode==CEC_OVERFLOW)
        printf("オーバーフローが起こりました\n");
    printf("テーブルの使用率= %f %%\n",
         100.0*MaxCodeTableSize/CODE_TABLE_SIZE);
    if (sz==0) return 1;
    printf("sz=%.0f\n",sz);
    for (i=0;i<5;i++) {
        NumToComb_r(tbl,r,(INDEX)(NextUnif()*sz));
        for (j=0;j<10;j++) printf("%2d ",r[j]);
        printf("\n");
    }
    return 0;
}

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

テーブルの使用率= 95.312500 %
sz=17310309456440
 1 15 23 25 41 44 56 79 85 92 
 6  7 16 19 22 35 40 42 54 65 
15 17 23 32 53 65 69 74 79 92 
 3 11 25 39 53 56 59 70 73 82 
 1 17 43 49 58 69 78 82 91 95

r に対する扱える n の最大値とその時の組み合わせ数

以下は、Ｃ言語としてコンパイルし、code_t を使用した場合である。 Ｃ＋＋としてコンパイルした場合や、〜_r 関数を使用しなければ、r が小さい場合、 オーバーフローするまで、もっと大きい n が扱える。 また、n が小さければ、この表に書いてあるものより大きい r を扱うこともできる。
InitRepe( ) で10000 を超える n を扱える r の行は省略している。

max.c : r に対する扱える n の最大値を得るプログラム

【Ｃ デフォルト 】
#define INDEX unsigned
InitComb(1278, 1) = InitRepe(1278, 1) = InitPart(1277, 2) = 1278
InitComb( 639, 2) = InitRepe( 638, 2) = InitPart( 637, 3) = 203841
InitComb( 426, 3) = InitRepe( 424, 3) = InitPart( 423, 4) = 12794200
InitComb( 321, 4) = InitRepe( 318, 4) = InitPart( 317, 5) = 434171760
InitComb( 222, 5) = InitRepe( 218, 5) = InitPart( 217, 6) = 4294249674
InitComb( 123, 6) = InitRepe( 118, 6) = InitPart( 117, 7) = 4249404082
InitComb(  83, 7) = InitRepe(  77, 7) = InitPart(  76, 8) = 4151918628
InitComb(  63, 8) = InitRepe(  56, 8) = InitPart(  55, 9) = 3872894697
InitComb(  52, 9) = InitRepe(  44, 9) = InitPart(  43,10) = 3679075400
InitComb(  46,10) = InitRepe(  37,10) = InitPart(  36,11) = 4076350421
InitComb(  42,11) = InitRepe(  32,11) = InitPart(  31,12) = 4280561376
InitComb(  39,12) = InitRepe(  28,12) = InitPart(  27,13) = 3910797436
InitComb(  37,13) = InitRepe(  25,13) = InitPart(  24,14) = 3562467300
InitComb(  36,14) = InitRepe(  23,14) = InitPart(  22,15) = 3796297200
InitComb(  35,15) = InitRepe(  21,15) = InitPart(  20,16) = 3247943160
InitComb(  35,16) = InitRepe(  20,16) = InitPart(  19,17) = 4059928950
InitComb(  34,17) = InitRepe(  18,17) = InitPart(  17,18) = 2333606220
InitComb(  34,18) = InitRepe(  17,18) = InitPart(  16,19) = 2203961430
InitPerm(2558, 1) = 2558
InitPerm(1278, 2) = 1632006
InitPerm( 852, 3) = 616294200
InitPerm( 257, 4) = 4261347840
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

【Ｃ＋＋ デフォルト 】
#define INDEX unsigned
InitComb(2954, 3) = InitRepe(2952, 3) = InitPart(2951, 4) = 4291795704
InitComb( 568, 4) = InitRepe( 565, 4) = InitPart( 564, 5) = 4291262010
InitComb( 222, 5) = InitRepe( 218, 5) = InitPart( 217, 6) = 4294249674
InitComb( 123, 6) = InitRepe( 118, 6) = InitPart( 117, 7) = 4249404082
InitComb(  83, 7) = InitRepe(  77, 7) = InitPart(  76, 8) = 4151918628
InitComb(  63, 8) = InitRepe(  56, 8) = InitPart(  55, 9) = 3872894697
InitComb(  52, 9) = InitRepe(  44, 9) = InitPart(  43,10) = 3679075400
InitComb(  46,10) = InitRepe(  37,10) = InitPart(  36,11) = 4076350421
InitComb(  42,11) = InitRepe(  32,11) = InitPart(  31,12) = 4280561376
InitComb(  39,12) = InitRepe(  28,12) = InitPart(  27,13) = 3910797436
InitComb(  37,13) = InitRepe(  25,13) = InitPart(  24,14) = 3562467300
InitComb(  36,14) = InitRepe(  23,14) = InitPart(  22,15) = 3796297200
InitComb(  35,15) = InitRepe(  21,15) = InitPart(  20,16) = 3247943160
InitComb(  35,16) = InitRepe(  20,16) = InitPart(  19,17) = 4059928950
InitComb(  34,17) = InitRepe(  18,17) = InitPart(  17,18) = 2333606220
InitComb(  34,18) = InitRepe(  17,18) = InitPart(  16,19) = 2203961430
InitPerm(1626, 3) = 4291014000
InitPerm( 257, 4) = 4261347840
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

【 #define INDEX double 】
#define INDEX double
InitComb( 639, 1) = InitRepe( 639, 1) = InitPart( 638, 2) = 639
InitComb( 320, 2) = InitRepe( 319, 2) = InitPart( 318, 3) = 51040
InitComb( 214, 3) = InitRepe( 212, 3) = InitPart( 211, 4) = 1610564
InitComb( 162, 4) = InitRepe( 159, 4) = InitPart( 158, 5) = 27646920
InitComb( 131, 5) = InitRepe( 127, 5) = InitPart( 126, 6) = 297602656
InitComb( 110, 6) = InitRepe( 105, 6) = InitPart( 104, 7) = 2141851635
InitComb(  96, 7) = InitRepe(  90, 7) = InitPart(  89, 8) = 11919192480
InitComb(  86, 8) = InitRepe(  79, 8) = InitPart(  78, 9) = 53060358690
InitComb(  78, 9) = InitRepe(  70, 9) = InitPart(  69,10) = 182364632450
InitComb(  72,10) = InitRepe(  63,10) = InitPart(  62,11) = 536211932256
InitComb(  67,11) = InitRepe(  57,11) = InitPart(  56,12) = 1285063345176
InitComb(  63,12) = InitRepe(  52,12) = InitPart(  51,13) = 2668424446233
InitComb(  60,13) = InitRepe(  48,13) = InitPart(  47,14) = 5166863427600
InitComb(  57,14) = InitRepe(  44,14) = InitPart(  43,15) = 7694644696200
InitComb(  55,15) = InitRepe(  41,15) = InitPart(  40,16) = 11899700525790
InitComb(  54,16) = InitRepe(  39,16) = InitPart(  38,17) = 21094923659355
InitComb(  52,17) = InitRepe(  36,17) = InitPart(  35,18) = 21945588357420
InitComb(  51,18) = InitRepe(  34,18) = InitPart(  33,19) = 27900908274925
InitComb(  50,19) = InitRepe(  32,19) = InitPart(  31,20) = 30405943383200
InitComb(  50,20) = InitRepe(  31,20) = InitPart(  30,21) = 47129212243960
InitComb(  49,21) = InitRepe(  29,21) = InitPart(  28,22) = 39049918716424
InitComb(  49,22) = InitRepe(  28,22) = InitPart(  27,23) = 49699896548176
InitComb(  48,23) = InitRepe(  26,23) = InitPart(  25,24) = 30957699535776
InitComb(  48,24) = InitRepe(  25,24) = InitPart(  24,25) = 32247603683100
InitComb(  48,25) = InitRepe(  24,25) = InitPart(  23,26) = 30957699535776
InitPerm(1279, 1) = 1279
InitPerm( 639, 2) = 407682
InitPerm( 426, 3) = 76765200
InitPerm( 320, 4) = 10290276480
InitPerm( 257, 5) = 1078121003520
InitPerm( 214, 6) = 89490569913360
InitPerm( 184, 7) = 6361571518323840
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
【Ｃ＋＋ #define INDEX double 】
#define INDEX double
InitComb(4045, 5) = InitRepe(4041, 5) = InitPart(4040, 6) = 9001965160097559
InitComb(1368, 6) = InitRepe(1363, 6) = InitPart(1362, 7) = 9003589632161124
InitComb( 645, 7) = InitRepe( 639, 7) = InitPart( 638, 8) = 8918666166467520
InitComb( 375, 8) = InitRepe( 368, 8) = InitPart( 367, 9) = 8996714454741750
InitComb( 249, 9) = InitRepe( 241, 9) = InitPart( 240,10) = 8760212643481299
InitComb( 182,10) = InitRepe( 173,10) = InitPart( 172,11) = 8543814344395330
InitComb( 143,11) = InitRepe( 133,11) = InitPart( 132,12) = 8634941152058949
InitComb( 118,12) = InitRepe( 107,12) = InitPart( 106,13) = 8531742652084314
InitComb( 101,13) = InitRepe(  89,13) = InitPart(  88,14) = 8160963550905900
InitComb(  89,14) = InitRepe(  76,14) = InitPart(  75,15) = 7632612327410136
InitComb(  81,15) = InitRepe(  67,15) = InitPart(  66,16) = 8144022047817960
InitComb(  75,16) = InitRepe(  60,16) = InitPart(  59,17) = 8550047575185300
InitComb(  70,17) = InitRepe(  54,17) = InitPart(  53,18) = 7877932561061640
InitComb(  66,18) = InitRepe(  49,18) = InitPart(  48,19) = 6848956078664700
InitComb(  64,19) = InitRepe(  46,19) = InitPart(  45,20) = 8719878125622720
InitComb(  61,20) = InitRepe(  42,20) = InitPart(  41,21) = 6236646703759395
InitComb(  60,21) = InitRepe(  40,21) = InitPart(  39,22) = 7984465725343800
InitComb(  59,22) = InitRepe(  38,22) = InitPart(  37,23) = 8964377427999630
InitComb(  58,23) = InitRepe(  36,23) = InitPart(  35,24) = 8799226775309880
InitComb(  57,24) = InitRepe(  34,24) = InitPart(  33,25) = 7522327487513475
InitComb(  56,25) = InitRepe(  32,25) = InitPart(  31,26) = 5574440580220512
InitComb(  56,26) = InitRepe(  31,26) = InitPart(  30,27) = 6646448384109072
InitComb(  56,27) = InitRepe(  30,27) = InitPart(  29,28) = 7384942649010080
InitComb(  56,28) = InitRepe(  29,28) = InitPart(  28,29) = 7648690600760440
InitComb(  56,29) = InitRepe(  28,29) = InitPart(  27,30) = 7384942649010080
InitPerm(9743, 4) = 9005406635906040
InitPerm(1554, 5) = 9004460205787200
InitPerm( 458, 6) = 8931244367878560
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

【 #define INDEX __int64 】
InitComb( 639, 1) = InitRepe( 639, 1) = InitPart( 638, 2) = 639
InitComb( 320, 2) = InitRepe( 319, 2) = InitPart( 318, 3) = 51040
InitComb( 214, 3) = InitRepe( 212, 3) = InitPart( 211, 4) = 1610564
InitComb( 162, 4) = InitRepe( 159, 4) = InitPart( 158, 5) = 27646920
InitComb( 131, 5) = InitRepe( 127, 5) = InitPart( 126, 6) = 297602656
InitComb( 110, 6) = InitRepe( 105, 6) = InitPart( 104, 7) = 2141851635
InitComb(  96, 7) = InitRepe(  90, 7) = InitPart(  89, 8) = 11919192480
InitComb(  86, 8) = InitRepe(  79, 8) = InitPart(  78, 9) = 53060358690
InitComb(  78, 9) = InitRepe(  70, 9) = InitPart(  69,10) = 182364632450
InitComb(  72,10) = InitRepe(  63,10) = InitPart(  62,11) = 536211932256
InitComb(  67,11) = InitRepe(  57,11) = InitPart(  56,12) = 1285063345176
InitComb(  63,12) = InitRepe(  52,12) = InitPart(  51,13) = 2668424446233
InitComb(  60,13) = InitRepe(  48,13) = InitPart(  47,14) = 5166863427600
InitComb(  57,14) = InitRepe(  44,14) = InitPart(  43,15) = 7694644696200
InitComb(  55,15) = InitRepe(  41,15) = InitPart(  40,16) = 11899700525790
InitComb(  54,16) = InitRepe(  39,16) = InitPart(  38,17) = 21094923659355
InitComb(  52,17) = InitRepe(  36,17) = InitPart(  35,18) = 21945588357420
InitComb(  51,18) = InitRepe(  34,18) = InitPart(  33,19) = 27900908274925
InitComb(  50,19) = InitRepe(  32,19) = InitPart(  31,20) = 30405943383200
InitComb(  50,20) = InitRepe(  31,20) = InitPart(  30,21) = 47129212243960
InitComb(  49,21) = InitRepe(  29,21) = InitPart(  28,22) = 39049918716424
InitComb(  49,22) = InitRepe(  28,22) = InitPart(  27,23) = 49699896548176
InitComb(  48,23) = InitRepe(  26,23) = InitPart(  25,24) = 30957699535776
InitComb(  48,24) = InitRepe(  25,24) = InitPart(  24,25) = 32247603683100
InitComb(  48,25) = InitRepe(  24,25) = InitPart(  23,26) = 30957699535776
InitPerm(1279, 1) = 1279
InitPerm( 639, 2) = 407682
InitPerm( 426, 3) = 76765200
InitPerm( 320, 4) = 10290276480
InitPerm( 257, 5) = 1078121003520
InitPerm( 214, 6) = 89490569913360
InitPerm( 184, 7) = 6361571518323840
InitPerm( 162, 8) = 397988967600806400
InitPerm( 132, 9) = 9206492916741120000
InitPerm(  83,10) = 8826447557543616000
InitPerm(  58,11) = 9088747467351552000
InitPerm(  43,12) = 7347251430341222400
InitPerm(  35,13) = 9193186188426240000
InitPerm(  29,14) = 6761440164390912000
InitPerm(  25,15) = 4274473667143680000
InitPerm(  23,16) = 5129368400572416000
InitPerm(  21,17) = 2128789257154560000
InitPerm(  21,18) = 8515157028618240000
InitPerm(  20,19) = 2432902008176640000
InitPerm(  20,20) = 2432902008176640000

【Ｃ＋＋ #define INDEX __int64 】
InitComb(4337, 6) = InitRepe(4332, 6) = InitPart(4331, 7) = 9210884681005865704
InitComb(1733, 7) = InitRepe(1727, 7) = InitPart(1726, 8) = 9202167919706100768
InitComb( 887, 8) = InitRepe( 880, 8) = InitPart( 879, 9) = 9207044098280898870
InitComb( 534, 9) = InitRepe( 526, 9) = InitPart( 525,10) = 9092292741062601356
InitComb( 361,10) = InitRepe( 352,10) = InitPart( 351,11) = 9134638038697149616
InitComb( 265,11) = InitRepe( 255,11) = InitPart( 254,12) = 9187507719876570240
InitComb( 206,12) = InitRepe( 195,12) = InitPart( 194,13) = 8795548359217331075
InitComb( 169,13) = InitRepe( 157,13) = InitPart( 156,14) = 9176358300744339432
InitComb( 143,14) = InitRepe( 130,14) = InitPart( 129,15) = 8887821571512103935
InitComb( 125,15) = InitRepe( 111,15) = InitPart( 110,16) = 9064807833193439800
InitComb( 111,16) = InitRepe(  96,16) = InitPart(  95,17) = 8156833787798824590
InitComb( 101,17) = InitRepe(  85,17) = InitPart(  84,18) = 7995995501984016450
InitComb(  94,18) = InitRepe(  77,18) = InitPart(  76,19) = 9007607943130625829
InitComb(  88,19) = InitRepe(  70,19) = InitPart(  69,20) = 8910491434304783400
InitComb(  83,20) = InitRepe(  64,20) = InitPart(  63,21) = 8179808679272664720
InitComb(  79,21) = InitRepe(  59,21) = InitPart(  58,22) = 7449416156804224460
InitComb(  76,22) = InitRepe(  55,22) = InitPart(  54,23) = 7266758081613043600
InitComb(  74,23) = InitRepe(  52,23) = InitPart(  51,24) = 8249183865278257824
InitComb(  72,24) = InitRepe(  49,24) = InitPart(  48,25) = 7950261662089028100
InitComb(  70,25) = InitRepe(  46,25) = InitPart(  45,26) = 6455761770304780752
InitComb(  69,26) = InitRepe(  44,26) = InitPart(  43,27) = 7023301266595310928
InitComb(  68,27) = InitRepe(  42,27) = InitPart(  41,28) = 6808417652963570336
InitComb(  67,28) = InitRepe(  40,28) = InitPart(  39,29) = 5864393356544251760
InitComb(  67,29) = InitRepe(  39,29) = InitPart(  38,30) = 7886597962249166160
InitComb(  66,30) = InitRepe(  37,30) = InitPart(  36,31) = 5516694892996182896
InitComb(  66,31) = InitRepe(  36,31) = InitPart(  35,32) = 6406484391866534976
InitComb(  66,32) = InitRepe(  35,32) = InitPart(  34,33) = 7007092303604022630
InitComb(  66,33) = InitRepe(  34,33) = InitPart(  33,34) = 7219428434016265740
InitComb(  66,34) = InitRepe(  33,34) = InitPart(  32,35) = 7007092303604022630
InitPerm(6210, 5) = 9220585194601079040
InitPerm(1450, 6) = 9198343437354036000
InitPerm( 515, 7) = 9222879462222182400
InitPerm( 238, 8) = 9140646456023322240
InitPerm( 132, 9) = 9206492916741120000
InitPerm(  83,10) = 8826447557543616000
InitPerm(  58,11) = 9088747467351552000
InitPerm(  43,12) = 7347251430341222400
InitPerm(  35,13) = 9193186188426240000
InitPerm(  29,14) = 6761440164390912000
InitPerm(  25,15) = 4274473667143680000
InitPerm(  23,16) = 5129368400572416000
InitPerm(  21,17) = 2128789257154560000
InitPerm(  21,18) = 8515157028618240000
InitPerm(  20,19) = 2432902008176640000
InitPerm(  20,20) = 2432902008176640000

【#define INDEX unsigned short 】
InitComb(2556, 1) = InitRepe(2556, 1) = InitPart(2555, 2) = 2556
InitComb( 362, 2) = InitRepe( 361, 2) = InitPart( 360, 3) = 65341
InitComb(  74, 3) = InitRepe(  72, 3) = InitPart(  71, 4) = 64824
InitComb(  36, 4) = InitRepe(  33, 4) = InitPart(  32, 5) = 58905
InitComb(  25, 5) = InitRepe(  21, 5) = InitPart(  20, 6) = 53130
InitComb(  21, 6) = InitRepe(  16, 6) = InitPart(  15, 7) = 54264
InitComb(  19, 7) = InitRepe(  13, 7) = InitPart(  12, 8) = 50388
InitComb(  18, 8) = InitRepe(  11, 8) = InitPart(  10, 9) = 43758
InitComb(  18, 9) = InitRepe(  10, 9) = InitPart(   9,10) = 48620
InitComb(  18,10) = InitRepe(   9,10) = InitPart(   8,11) = 43758
InitPerm(5116, 1) = 5116
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

【Ｃ＋＋ #define INDEX unsigned short 】
#define INDEX unsigned short
InitComb( 362, 2) = InitRepe( 361, 2) = InitPart( 360, 3) = 65341
InitComb(  74, 3) = InitRepe(  72, 3) = InitPart(  71, 4) = 64824
InitComb(  36, 4) = InitRepe(  33, 4) = InitPart(  32, 5) = 58905
InitComb(  25, 5) = InitRepe(  21, 5) = InitPart(  20, 6) = 53130
InitComb(  21, 6) = InitRepe(  16, 6) = InitPart(  15, 7) = 54264
InitComb(  19, 7) = InitRepe(  13, 7) = InitPart(  12, 8) = 50388
InitComb(  18, 8) = InitRepe(  11, 8) = InitPart(  10, 9) = 43758
InitComb(  18, 9) = InitRepe(  10, 9) = InitPart(   9,10) = 48620
InitComb(  18,10) = InitRepe(   9,10) = InitPart(   8,11) = 43758
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

おわりに

このプログラムを理解しようとするならば、重複組み合わせから始める とよい。具体的には test.c を実行し repe demo を選択して、 重複組み合わせと出力される表の対応関係を見るとよい。

プログラムの NumTo????( ) と ????ToNum( ) は表を使っている。表 の使用方法は、関数が短いので容易に理解できる(と思う)。

一方、Init????( )が行っている表の作成はかなり複雑で、私も 試行錯誤でこの方法を見つけた。

perm は後から付け加えた例外的なもので、計算の方法が他の ３つとは大幅に違い、表も１つしか持っていない。