2
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ If you know that the keys come from some set with at most $N$ elements, and there are $k$ elements in each subset, then you may have to use $k\lceil \log_2 N\rceil$ bits for the unique subset identifiers in the worst case. A small saving is possible, but this is essentially tight from the information-theoretic bounds; it corresponds to simply running together the bit strings representing key identifiers. However, if the number $S$ of subsets is much smaller than $\binom{N}{k}$, then you could use $\lceil \log_2 S \rceil$ bits and this is optimal. $\endgroup$ – András Salamon Sep 8 '13 at 15:11
  • $\begingroup$ Cool, but how did you calculate the complexity? And when you gave $$k\lceil {log}_{2}N \rceil$$, does it mean that the complexity is $$O(k {log}_{2}N)$$ ? (If you can post it as an answer it would be great ... I can tick it as accepted :) ) $\endgroup$ – FearUs Sep 8 '13 at 21:27
  • $\begingroup$ Please keep in mind that K is fixed but N changes over time. $\endgroup$ – FearUs Sep 8 '13 at 22:04
  • 1
    $\begingroup$ Please don't cross-post/duplicate the same question on two sites. This is especially frowned upon when (1) you are posting the same question on two sites within a short time period, or (2) you have already gotten answers on one site. Here, you asked on SO only yesterday, and you already got at least one answer. Instead of cross-posting, you should click the "flag" button underneath your question to ask the moderators to migrate the question to another site. $\endgroup$ – D.W. Sep 9 '13 at 2:21
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok, so let's suppose that $m = {m \choose k}$. It would be asymptotic to what? $\endgroup$ – FearUs Sep 9 '13 at 6:03
  • $\begingroup$ ^ I'm talking about $m$ $\endgroup$ – FearUs Sep 9 '13 at 6:10
  • 1
    $\begingroup$ See the formula: plug in $m={n \choose k}$ into $O(m)$ or $O(mk)$ or $O(mk \lg n)$ (depending upon what model you're in and what you want to count and not count). What do you get? $\endgroup$ – D.W. Sep 9 '13 at 6:42
  • $\begingroup$ Ok, I am sorry I got confused and I guess I didn't understand your answer at the beginning. Now it's clear. It's $O({n \choose k})$. Thanks a lot. On a side note, why if $n \le {2}^{64}$ then it takes $O(lg n)$ to store an element of S ? $\endgroup$ – FearUs Sep 9 '13 at 7:06
  • 1
    $\begingroup$ @FearUs, it's just a question about how we count space. If $n \le 2^{64}$, then each element of $S$ can be stored in 64 bits (one word), so we can treat the amount of space to store a single element as $O(1)$ space, or the amount of space to store a subset of size $k$ as $O(k)$ space. If $n$ is super-large (way larger than $2^{64}$), this is no longer accurate -- but that probably won't come up for many applications. $\endgroup$ – D.W. Sep 9 '13 at 7:09

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.