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)

Improve this question
$\endgroup$
4
  • 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
    Commented Sep 8, 2013 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$
    – firas
    Commented Sep 8, 2013 at 21:27
  • $\begingroup$ Please keep in mind that K is fixed but N changes over time. $\endgroup$
    – firas
    Commented Sep 8, 2013 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. ♦
    Commented Sep 9, 2013 at 2:21

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Ok, so let's suppose that $m = {m \choose k}$. It would be asymptotic to what? $\endgroup$
    – firas
    Commented Sep 9, 2013 at 6:03
  • $\begingroup$ ^ I'm talking about $m$ $\endgroup$
    – firas
    Commented Sep 9, 2013 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. ♦
    Commented Sep 9, 2013 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$
    – firas
    Commented Sep 9, 2013 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. ♦
    Commented Sep 9, 2013 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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