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

概要

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

例えぱ、0 1 2 3 のように 4 種類(N=4,N>0)の要素があるものとし、これから 3 つ要素(R=3,0<R<=N)を取り出して並べる場合を考える。
並べ方は、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)

となる。目的は、

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

並べ方の辞書順の番号を求める PermToNum( )

逆に辞書順の番号から並べ方を求める NumToPerm( )

応用例

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

簡略版プログラム

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

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

unsigned PermToNum(const unsigned char*vec) {
    int i,j,k; unsigned u=0;
    for (i=0;i<R;i++) {
        for (k=vec[i],j=0;j<i;j++) if (vec[j]<vec[i]) k--;
        if (k) u+=TableA[i][k-1];
    }
    return u;
}

void NumToPerm(unsigned char*vec,unsigned num) {
    int i,j,k,r=R; char f[N];
    for (j=0;j<N;j++) f[j]=0;
    for (i=0;i<r;i++) {
        for (k=0;TableA[i][k]<=num;k++) ;
        if (k) num-=TableA[i][k-1];
        for (j=0;k>=0;k--,j++) while (f[j]) j++;
        f[--j]=1; vec[i]=(unsigned char)j;
    }
}

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