-1
$\begingroup$

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$

$\endgroup$
13
  • 2
    $\begingroup$ 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$ $\endgroup$ Apr 16 '11 at 0:33
  • 2
    $\begingroup$ What is the relationship between A, B, and C? $\endgroup$ Apr 16 '11 at 7:29
  • 2
    $\begingroup$ @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|$. $\endgroup$ Apr 16 '11 at 7:33
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 16 '11 at 11:14
  • 3
    $\begingroup$ (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. $\endgroup$ Apr 21 '11 at 11:18
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – jmacedo
    Apr 23 '11 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.