DouKaku? 1944 yooskeh: hashは問題のハッシュ関数そのままの実...(「組合せ型の最小完全ハッシュ関数」の逆関数)

Comment detail

hashは問題のハッシュ関数そのままの実装です。

?- hash(5, 2, [0, 1, 0, 1, 0], X).
X = 4

Prologのパターンマッチとバックトラックにより
逆関数としても使えます。

?- hash(5, 2, L, 4).
L = [0, 1, 0, 1, 0]

これはこれで面白いのですが
結局のところ順列を作りつつ調べていくので
n, mが大きくなると使い物になりません。

その点unhashは双方向ではありませんが
combを考えなければ計算量は線形です。

あと、combは一応メモ化してますが、
たぶん計算方法が良くないです。

%%	comb(+N, +K, ?C)

:- dynamic comb/3.

comb(_, 0, 1) :- !.
comb(N, K, X) :-
	N0 is N - 1,
	K0 is K - 1,
	comb(N0, K0, X0),
	X is X0 * N / K,
	asserta(comb(N, K, X) :- !).

%%	hash(+N, +M, ?BitList, ?Hash)

hash(0, 0, [], 0) :- !.
hash(N, M, [1|Bs], H) :-
	succ(M0, M),
	succ(N0, N),
	comb(N0, M, C),
	hash(N0, M0, Bs, H0),
	H is C + H0.
hash(N, M, [0|Bs], H) :-
	succ(N0, N),
	hash(N0, M, Bs, H).

%%	unhash(+N, +M, +Hash, ?BitList)

unhash(0, 0, _, []) :- !.
unhash(N, M, H, [B|Bs]) :-
	N0 is N - 1,
	(   N > 0,
	    comb(N0, M, C),
	    H >= C
	->  B = 1,
	    H0 is H - C,
	    M0 is M - 1,
	    unhash(N0, M0, H0, Bs)
	;   B = 0,
	    unhash(N0, M, H, Bs)
	).

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq