[Solved]: Set combination data structure (And storage complexity)

Problem Detail: 

I have already posted this question on Stackoverflow, but I'm starting to think that this is the right place.

I have a problem where I am required to associate unique combinations from a set (unique subsets) to a given value. e.g.: Let S={a, b, c, d}, the required data structure should perform the following:

Key -> value

{a,b} -> value1 {a,c} -> value2 {c,d} -> value3 

• Property 1: The length of the set in the key is fixed (In this example it's fixed to 2).
• Property 2: The data structure does not hold all possible subsets of S.

Question 1: What is the storage complexity of a simple Map holding these values? O(N!)? (given that |S| = N and it's not fixed)

Question 2: Is there any efficient data structure that could store such elements? (The most important efficiency would be required in storage complexity)

Asked By : FearUs

Answered By : D.W.

Question 1: The storage complexity of a map for holding these values is $\Theta(m)$, where $m$ is the number of entries in the map, assuming we don't count the space to store the sets themselves, and assuming we store them in a hash table (or similar data structure).

This doesn't include the space to store the sets in the keys, as those presumably already exist. If you want to include that space as well in your estimate of the space complexity, then we need at most $\Theta(m)$ space for the map, plus $\Theta(mk)$ space to hold the sets (assuming each set contains $k$ elements), for a total of $\Theta(mk)$ space. I am assuming that each element of $S$ can be stored in a single word ($\Theta(1)$ space), e.g., that $n \le 2^{64}$. If $n$ is huge, so that an element of $S$ cannot be stored in a single word, a better estimate of the total space usage is $\Theta(mk \lg n)$, since it takes $\Theta(\lg n)$ bits to store a single element of $S$, each subset of $k$ elements takes $\Theta(k \lg n)$ bits, and there are $m$ entries in the map, each of which requires $\Theta(k \lg n)$ bits to store it.

The number of unique subsets of size $k$, out of a universe of $n$ items, is ${n \choose k}$. Therefore, if you know that the keys are subsets of size $k$, you know that $m \le {n \choose k}$. But you mentioned in the question that the number of entries in the map is less than all possible subsets of size $k$, so this isn't helpful.

Question 2: Yes, a hash table would be an efficient data structure to store these elements. There's a straightforward way to define a hash function on subsets of $S$, so you can use that to build a hash table. A hash table achieves the space complexities listed above.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14208