My understanding of the problem
So, as I understand your question, the possible "keys" used to retrieve your data are a choice of k values among n values.
With :
- n from 0 up to n-1
- no repeating values
- only the values present in the keys matters, not the order of them
Simple proposition
Let start by a simple proposition as a reference point.
You can consider that the values present in your "key" are the bit that must be set to 1 in an 'n' bits address :
- conversion from key to address seems quite easy
- memory size is 2^n words (so quite a lot of space is wasted)
Divide and conquer : n=16, k=2
Lets take this particular case : n=16, k=2.
With the preceding solution, we use 2^16 words of memory, whereas there is only 16*15/2 = 120 possible keys.
For such a case, a divide and conquer strategy can be :
- either the two value are both in the first part of the possible values (0 up to 7)
- either they are both in the second part of the possible values (8 up to 15)
- either one value is in the first part, and the othr value in the second part.
Using this preliminary test, you can in this case use :
- one 8 bit address memory for case 1 (cf. initial simple solution but with n=8 instead of 16)
- one 8 bit address memory for case 2 (idem)
- one special case where you have 8 possible choice for the first part, and 8 other for the second, thus an additionnal 8*8=64 words memory (6 bits address, first 3 bits correspond to the value between 0 and 7 for the first part, and the 3 others are a value between 0 and 7 corresponding to the position of the value from 8 up to 15).
2^8 + 2^8 + 64 = 576 words
Divide and conquer : n=16, k=3
Lets try to do the same with a bigger value of k : k = 3
The smallest value of the key is between 0 and 13 (because if this is 13, the 2 other values will be 14 and 15). This first set bit can be found quite easily.
So we can reduce the problem to 14 sub problems (all with k=2, so we can use the previously studied case to optimise memory usage for each of them) :
- k=2, n=15 (between 1 and 15)
- k=2, n=14 (between 2 and 15)
- k=2, n=13 (between 3 and 15)
- ...
- k=2, n=4 (between 12 and 15)
- k=2, n=3 (between 13 and 15)
- k=2, n=2 (between 14 and 15, so only one possible case)
I have not done the math, but this probably gives a better memory usage than the initial simple solution.
"Symmetry" : n=6, k=4
This si choosing 4 values among 6, so it is equivalent to decide what are the 2 values not choosen, so we are in a case similar to "n=6, k=2" as the memory optimisation is concerned.
Hope this helps.