重複組合せの最小完全ハッシュ関数とその逆変換(列挙)の簡略版

概要

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

例えぱ、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)を同じものと考える。目的は、

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

昇順とは限らない取り出し方の番号を求めるRepeToNum( )

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

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

応用例

全重複組合せの列挙
一個の乱数からランダムな重複組合せを生成する
重複組合せの度数ソート
重複組合せの幅優先探索でハッシュ関数として使用する

簡略版プログラム

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

unsigned InitRepe(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 RepeToNum(const unsigned char*const vec) {
    int i,j; unsigned char k,sorted[R]; unsigned num=0;
    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++) num+=TableA[i][sorted[i]];
    return num;
}

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

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

int main(void) {
    int i,r=R; unsigned k,sz=InitRepe(); unsigned char vec[R];
    if (sz==0) { printf("Error.\n"); return 1; }
    for (k=0;k<sz;k++) {
        NumToRepe(vec,k);
        printf("%4u -> (%u", k,vec[0]);
        for (i=1;i<r;i++) printf(",%u",vec[i]);
        printf(") -> %4u\n", RepeToNumFast(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