0
$\begingroup$

Given a set of many variables $S=\{x_1,x_2, ...., x_i\}$, and any subset $S'$ of $S$, I need a function $f$ which maps $S'$ to a value $x$ and a function $f'$ which maps $x$ back to set $S'$.

I know my question can be solved with Gödel_numbering, but it will consume a lot of space and the computation cost is quite high when the size of $S'$ is big.

Is there any relationship the values in $S$ can satisfy such that we can make function $f$ and $f'$ very easy?

I tried making all values in S to be even, odd or prime and function f as sum. But it clearly does not work.

Improve this question
$\endgroup$
9
  • $\begingroup$ This seems to be basically the same question as this one on Mathematics: How to encode many integer easily. If you look at the recommendations related to cross-posting, you should probably indicate that you have posted to both sites. See, for example: Cross posts to Math SE. $\endgroup$
    – Martin Sleziak
    Commented Nov 17, 2020 at 13:09
  • $\begingroup$ @MartinSleziak Thanks. I was about to say this. I know there is a similar question link posted many years ago. But my case is different, I allow values in S to satisfy some requirements or relationship. I hope that it could make the problem easier. $\endgroup$
    – Rise of Kingdom
    Commented Nov 17, 2020 at 13:14
  • $\begingroup$ @MartinSleziak Thanks for your suggestions. I have deleted my old question posted in MATH SE. $\endgroup$
    – Rise of Kingdom
    Commented Nov 17, 2020 at 13:16
  • $\begingroup$ Unless I am mistaken, a comment linking to this question was posted here before: Encoding $n$ natural numbers into one and back. It seems that it was deleted for some reason. $\endgroup$
    – Martin Sleziak
    Commented Nov 17, 2020 at 13:56
  • $\begingroup$ @MartinSleziak I post this question after I have look at the question you link to in your comments. The solution for that question is still very costly. I allow values in S to satisfy some requirements or relationship. I hope that it could make the problem easier. $\endgroup$
    – Rise of Kingdom
    Commented Nov 17, 2020 at 14:02

1 Answer 1

Reset to default
0
$\begingroup$

This is inspired by answers in the other linked threads. You can let $f(S') = \sum_{x_j \in S'} 2^{j-1}$.

If you let your set only contain powers of 2, i.e. $S = \{ 1, 2, 4, 8, \ldots , 2^i\}$, then $f(S') = \sum_{x_j \in S'} x_j$, the sum of all numbers in $S'$.

Note that this is the same as interpreting $S'$ as a length $i$ binary number where the $j$th bit is 1 if $x_j \in S'$ and 0 otherwise. Note that there are $2^i$ different subsets of $S$ so you need a binary number of length at least $i$ to be able to represent all possible subsets.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer. The function is quite simple. The only issue is the length of bits increases linearly with the size of S'. Can we find a good way to reduce the memory cost (e.g., increasing sub-linearly)? $\endgroup$
    – Rise of Kingdom
    Commented Nov 18, 2020 at 6:47
  • $\begingroup$ Another possible issue is that the number will goes very big such that 64 bits machine cannot represent when the size of S is large. $\endgroup$
    – Rise of Kingdom
    Commented Nov 18, 2020 at 6:50
  • 5
    $\begingroup$ There are $2^{|S|}$ different subsets of $S$ so you need an $|S|$-bit number to be able to identify all possible subsets. $\endgroup$
    – Mattias Andersson
    Commented Nov 18, 2020 at 8:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .