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

概要

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

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

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

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

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

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

応用例

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

簡略版プログラム

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

unsigned InitComb(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 CombToNum(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]-i];
    return num;
}

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

void NumToComb(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+i);
    }
}

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