Set combination data structure (And storage complexity)

Question

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)

Answer 1

The number of distinct subsets of size k in a set of n items is n!/(k!*(n-k)!). This will also be the optimal storage complexity for a map storing the values.

You could use a forest of binary trees to represent subsets. Nodes will contain a key and two child pointers. Leaf nodes will represent subsets of size 1. Parent nodes on the level above leaf nodes will represent subsets of size 3 since they contain a key and points at two leaf nodes containing keys. The next level of parent nodes will represent subsets of size 7 and so on.

You will get a forest with n!/(k!*(n-k)!) possible root nodes. Your "simple map" will be a hash map that maps from root nodes to stored values.

To obtain optimal storage complexity you need to avoid duplication of equivalent nodes. When you create a node in your forest you have to check if you already have created a node representing the same subset. If an equivalent node exists you must reuse that instead of creating a new one. Thus a node could have many parents. (You might want to put nodes in hash tables to avoid duplication.) Because of the stated complexity the forest will be dominated by nodes at top level. Since each node is of fixed size the storage cost of the entire forest will be bounded by the number of root nodes multiplied by a constant.