algorithm - 分類用ハッシュ関数

Question

異なる数 $0 ~ 2^(n+1)-1$ の既知のセット $A$ が与えられます。バイナリ モードでは、要素が 0/1 の n 次元ベクトルです。$A$ の $m$ 個の個別の数を含む任意のサブセット $S$ に対して、$f(S)$ が $0,1,...,m-1 になるような関数 $f$ を見つけることは可能ですか? $、$f(A\S)$ が $0,1,...,m-1$ に入ってはいけません。関数 $f$ はできるだけ単純にする必要があります。線形の関数が推奨されます。ありがとう。

Answer 1

探しているキーワードは最小完全ハッシュ関数です。はい、特定のSに対して最小完全ハッシュ関数を構築することは常に可能です。