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

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

<p>I.e. for the subset $\{0,8,3\}$</p>

<p>$f(\{0,8,3\}) = 2^0 + 2^8 + 2^3$</p>

<p>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.</p>

CC BY-SA 3.0
2011-04-23T01:11:57.820Z
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
CC BY-SA 3.0
2011-04-16T15:45:58.587Z
2011-04-16T17:14:38.867Z
2011-04-16T17:14:38.867Z
Rehno Lindeque
<p>I would like to be able to map any subset of $S = \{0,..,m-1\}$ to an integer $k$.</p>

<p>$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.</p>

<p>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 </p>

<p>$\sum_{i=0}^{l-1} \binom{m}{i} $ and $\sum_{i=0}^{l} \binom{m}{i} $</p>

<p>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:</p>

<ul>
<li><p>$B \neq C \Rightarrow f(B) \neq f(C)$</p></li>
<li><p>The amplitude of codomain of $f$ must be  $\binom{m}{2}$</p></li>
<li><p>$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 \{&lt;,&gt;\} \wedge a_{i}$ satisifies this property $)$ </p></li>
</ul>

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

<p>$  f(\{0,3\}) = 3, f(\{0,2\}) = 2 , f(\{0,1\}) = 1$<br>
$  f(\{1,3\}) = 5, f(\{1,2\}) = 4$<br>
$  f(\{2,3\}) = 6$</p>

<p>$\binom{4}{2} = 6$</p>

CC BY-SA 3.0
2011-04-16T00:33:46.633Z
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
CC BY-SA 3.0
2011-04-16T01:13:44.977Z
this does not work because in this case $f(a,b) \neq f(b,a)$ and $\{a,b\}$ is a set
jmacedo
CC BY-SA 3.0
2011-04-16T07:29:31.603Z
What is the relationship between `A`, `B`, and `C`?
Peter Taylor
CC BY-SA 3.0
2011-04-16T07:33:13.037Z
@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|$.
Sadeq Dousti
CC BY-SA 3.0
2011-04-16T10:35:45.817Z
@joxnas, @Sadeq I gave a quick answer because I thought I didn't understand well the question (or there was something hidden in it), correct conditions for my function were: $0 \leq a \lt b \lt m$, and the Sadeq's min/max trick work perfectly if you want to write it as $f( \{ a,b \})$.
Marzio De Biasi
CC BY-SA 3.0
2011-04-16T11:14:53.013Z
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
CC BY-SA 3.0
2011-04-16T12:20:25.057Z
Also, @Kaveh, @joxnas, why the tags `cr.crypto-security` and `one-way-function`? I don't see anything in the problem statement which suggests that $f$ shouldn't be easily inverted.
Peter Taylor
CC BY-SA 3.0
2011-04-16T12:49:45.220Z
@joxnas Is your question related to the implementation of http://cstheory.stackexchange.com/questions/6025/finding-the-longest-path-between-two-nodes-in-a-bidirectional-unweighted-graph/6032#6032 ?
Marcus Ritt
CC BY-SA 3.0
2011-04-17T07:29:02.453Z
@Peter Taylor, I added `cr.crypto-security` because of one-way-function and hash-function tags.
Kaveh
CC BY-SA 3.0
2011-04-21T11:18:53.200Z
(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
CC BY-SA 3.0
2011-04-23T00:53:36.730Z
@Tsuyoshi Ito I tried to correct my question, but I don't know if It is formally correct, probably not. If you have a suggestion on how I could make it right, i would appreciate it. Sadeq's solution doesn't fit my needs.
jmacedo
CC BY-SA 3.0
2011-04-23T01:09:33.440Z
Voted to close as off-topic; based on the accepted answer, this is not research-level TCS.
Jukka Suomela
<co.combinatorics><hash-function>
Minimal perfect hash function from sets of integers to integers
jmacedo
# Minimal perfect hash function from sets of integers to integers

(Asked by: username_0 on 2011-04-15)

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$

**Tags:** co.combinatorics, hash-function

> **Comments:**
> **username_1**: 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$  
> **username_0**: this does not work because in this case $f(a,b) \neq f(b,a)$ and $\{a,b\}$ is a set  
> **username_2**: What is the relationship between `A`, `B`, and `C`?  
> **username_3**: @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|$.  
> **username_1**: @joxnas, @Sadeq I gave a quick answer because I thought I didn't understand well the question (or there was something hidden in it), correct conditions for my function were: $0 \leq a \lt b \lt m$, and the Sadeq's min/max trick work perfectly if you want to write it as $f( \{ a,b \})$.  
> **username_4**: 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.  
> **username_2**: Also, @username_6, @joxnas, why the tags `cr.crypto-security` and `one-way-function`? I don't see anything in the problem statement which suggests that $f$ shouldn't be easily inverted.  
> **username_5**: @joxnas Is your question related to the implementation of http://cstheory.stackexchange.com/questions/6025/finding-the-longest-path-between-two-nodes-in-a-bidirectional-unweighted-graph/6032#6032 ?  
> **username_6**: @username_2, I added `cr.crypto-security` because of one-way-function and hash-function tags.  
> **username_4**: (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.  
> **username_0**: @username_4 I tried to correct my question, but I don't know if It is formally correct, probably not. If you have a suggestion on how I could make it right, i would appreciate it. Sadeq's solution doesn't fit my needs.  
> **username_7**: Voted to close as off-topic; based on the accepted answer, this is not research-level TCS.  

---

## 1 answers

### Answer by username_8 on 2011-04-16. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_0**: 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  

---

