非負整数解の最小完全ハッシュ関数とその逆変換(列挙)の簡略版

概要

このＣ／Ｃ＋＋言語で書かれたソースプログラムは、非負整数解の最小完全ハッシュ関数(辞書順での順位)を求める。
また、最小完全ハッシュ関数の逆変換もできる。
そして０から順に最大値までをこの逆変換をすれば、非負整数解を全て列挙することができる。

例えぱ、3 個の球(SN=3,SN>=0)があるものとし、これを 3 つの箱 (SR=3,SR>=2)に分ける場合を考える。
分け方は、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 だからである。)

目的は、

テーブルを作成し何通りあるかを求める InitSolu( )

取り出し方に辞書順の番号を求める SoluToNum( )

逆に辞書順の番号から取り出し方を求めるNumToSolu( )

応用例

非負整数解の列挙
一個の乱数からランダムな非負整数解を生成する
非負整数解の度数ソート
非負整数解の幅優先探索でハッシュ関数として使用する

簡略版プログラム

/*
simple-s.c 非負整数解の最小完全ハッシュ関数とその逆変換(列挙)の簡略版
programmed by Isaku WADA isaku@pb4.so-net.ne.jp
*/
#include <stdio.h>
#define SN 3
#define SR 3
#if SN >= 256
 #error ' SN > 256 ' Out of unsigned char.
#endif
#define N (SN+1)
#define R (SR-1)
unsigned TableA[R][N];
unsigned TableB[R][N];

unsigned InitSolu(void) {
    int n=N,r=R,i,j; unsigned(*a)[N]=TableA,(*b)[N]=TableB;
    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;
    for (i=0;i<r;i++) for (j=1;j<n;j++) if (b[i][j]<=b[i][j-1]) return 0;
    return b[0][n-1];
}

unsigned SoluToNum(const unsigned char*vec) {
    int i,z=0; unsigned num=0;
    for (i=0;i<R;i++) num+=TableA[i][z+=vec[i]];
    return num;
}

void NumToSolu(unsigned char*vec,unsigned num) {
    int i,j=0,sum=SN,prev=0;
    for (i=0;i<R;i++) {
        while (TableB[i][j]<=num) j++;
        num-=TableA[i][j]; sum-=vec[i]=(unsigned char)(j-prev); prev=j;
    }
    vec[i]=(unsigned char)sum;
}

int main(void) {
    int i,sr=SR; unsigned s,sz=InitSolu(); unsigned char vec[SR];
    if (sz==0) { printf("Error.\n"); 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));
    }
    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