Data-structure for functions of independent sets Suppose I have a graph $G$, with nodes $\{1,2,\ldots,n\}$, subsets of nodes $\{b_1,\ldots,b_k\}$ and functions $\{f_1,\ldots,f_k\}$ where $f_i$ maps independent subsets of $b_i$ to reals. The operation on $f$ is setting or getting all values in "canonical order", ie, $\langle f(\emptyset),f(\{1\}),f(\{2\}),f(\{3\}),f(\{1,2\}),\ldots \rangle$.

What is a way to do this more efficiently than with an array of size $2^{|b_i|}$ for $f_i$? This comes up when counting independent sets on graphs
I wanted to post a comment, but with no "karma" it seems impossible... What about using dictionaries (hashmap, depending on the language you use) to store the values of your $f_i$ ? This way you don't have to know beforehand the size of the memory you will need, and gettin a function's value is not too slow.