「組合せ型の最小完全ハッシュ関数」の逆関数 in C DouKaku?

「組合せ型の最小完全ハッシュ関数」の逆関数

「組み合わせ型の最小完全ハッシュ関数」とは下のような「n個の値のうちm個が1で残りが0であるようなデータ」と整数とを対応づける関数です。下の例ではn=5でm=2になっています。 (「0以上n未満の整数から重複しないm個を選んだ組み合わせ」もデータとしては同じです)

>>> for xs in make_perm(5, 2):
	print xs, "=>", hash(xs, 5, 2)

	
[1, 1, 0, 0, 0] => 9
[1, 0, 1, 0, 0] => 8
[1, 0, 0, 1, 0] => 7
[1, 0, 0, 0, 1] => 6
[0, 1, 1, 0, 0] => 5
[0, 1, 0, 1, 0] => 4
[0, 1, 0, 0, 1] => 3
[0, 0, 1, 1, 0] => 2
[0, 0, 1, 0, 1] => 1
[0, 0, 0, 1, 1] => 0

「ハッシュ関数」というとデータが文字列であるものを連想しやすいですが、ここで扱う対象データは文字列ではありません。(ちなみに文字列のハッシュ関数は、異なる文字列が同じハッシュ値になることがあるので「完全」ではありません。)

さて、ここからが本題です。組み合わせのデータを与えると整数を返すのがこのハッシュ関数でした。この逆の関数、「整数xを与えると、hash(data) == xになるような組み合わせのデータdataを返す関数」を作ってください。

このお題はshuyoさんの提案を元に作成しました。ありがとうございました。

post comment

Posted feedbacks - C

第4引数にn以上のサイズのint型配列の先頭アドレスを与えるとその配列にデータが格納されるようになってます。

#include <stdlib.h>
#include <string.h>

void rev_hash(int dt, int n, int m, int *buf){
    int *selected, i, j;
    selected = (int *)malloc(sizeof(int) * m);
    for(i = 0; i < m; i++){
        selected[i] = i;
    }
    for(i = 0; i < dt; i++){
        int moveup = 0;
        for(j = 0; j < m - 1; j++, moveup++){
            if(selected[j] + 1 != selected[j + 1]){
                selected[j]++;
                break;
            }
        }
        if(j == m - 1){
            selected[j]++;
        }
        for(j = 0; j < moveup; j++){
            selected[j] = j;
        }
    }
    memset(buf, 0, sizeof(int) * n);
    for(i = 0; i < m; i++){
        buf[n - selected[i] - 1] = 1;
    }
    free(selected);
}

DouKaku?

「組合せ型の最小完全ハッシュ関数」の逆関数

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq