Minimal perfect hash function from sets of integers to integers

Question

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$

Answer 1

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.