# Minimal perfect hash function from sets of integers to integers

I would like to be able to map any subset of $S = \{0,..,m-1\}$ to an integer $k$.

$m$ will probably be 32 because $|\mathcal{P}(S)| = 2^m$ and i want to use a variable with 32 bits to store this value.

I know that given a set with $l$ elements, ( where each of its elements belongs to $\{0,..,m-1\}$ ) i can map its value between

$\sum_{i=0}^{l-1} \binom{m}{i}$ and $\sum_{i=0}^{l} \binom{m}{i}$

Which leaves me now with the problem: For a set of size $2$ where each element belongs to $\{0,..,m-1\}$, i need a function $f$ which satisfies:

• $B \neq C \Rightarrow f(B) \neq f(C)$

• The amplitude of codomain of $f$ must be $\binom{m}{2}$

• $f$ must not need to order the set to calculate the value - that is, $f = a_{1} \circ a_{2} \circ ... \circ a_{n} \Rightarrow \forall i , ( a_{i} \notin \{<,>\} \wedge a_{i}$ satisifies this property $)$

Here is an example of what should be a function like this: for $m=4$:

$f(\{0,3\}) = 3, f(\{0,2\}) = 2 , f(\{0,1\}) = 1$
$f(\{1,3\}) = 5, f(\{1,2\}) = 4$
$f(\{2,3\}) = 6$

$\binom{4}{2} = 6$

• Given m, and $a \neq b$, a trivial answer is: $f({a,b}) = \frac{m \times (m-1)}{2} - \frac{(m-a) \times (m-a-1)}{2} + b - a$ – Marzio De Biasi Apr 16 '11 at 0:33
• What is the relationship between A, B, and C? – Peter Taylor Apr 16 '11 at 7:29
• @joxnas: @Vor's solution works if you replace instances of "a" with min{a,b} and instances of "b" with max{a,b}. That is, $f(a,b)= \frac{(m-\min\{a,b\})(m+\min\{a,b\}-1)}{2}+ |b-a|$. – M.S. Dousti Apr 16 '11 at 7:33
• joxnas: I cannot understand the precise meaning of the condition “f must not need to order the set to calculate the value.” Does the solution in Sadeq’s comment satisfy the condition? If not, it is because the condition is not stated clearly, so please define the condition. – Tsuyoshi Ito Apr 16 '11 at 11:14
• (1) I removed [cr.crypto-security], [one-way-function] and [ramsey-theory], none of which has a clear connection to the question. (2) Without a clarification, I do not think that the question makes sense (see my comment on April 16). I voted to close it as not a real question. – Tsuyoshi Ito Apr 21 '11 at 11:18

Excuse me if this is a naive answer, I haven't read the problem very carefully and I've just had a beer ;)

Couldn't you just add up every element of the set as a power of two?

I.e. for the subset $\{0,8,3\}$

$f(\{0,8,3\}) = 2^0 + 2^8 + 2^3$

This doesn't require you to order the subset ($2^0 + 2^8 + 2^3 = 2^0 + 2^3 + 2^8$) and assigns a unique integer for every possible subset.

• Yes, this is right. This is a good solution, actually similar to the one I ended up using for my problem just some hours before you posted it. In my program, i used int variables to represent the sets. for example: $f(\{0\}) = 0001, f(\{1\}) = 0010, f(\{2\}) = 0100, f(\{3\}) = 1000$ which enabled me to do things like $f(\{a\} \cup A) = f(\{a\}) | f(A)$ ( | is the bitwise operator ), which gives correct results even if $a \in A$. $f(A \cup B )$ would be analogous – jmacedo Apr 23 '11 at 1:11