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さんの提案を元に作成しました。ありがとうございました。

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は一応メモ化してますが、
たぶん計算方法が良くないです。