Memory addressing method to allocate memory (static-hardware) for values corresponding to 'nCk' combination of values from 0 to n-1

Question

I need to find a memory addressing method to allocate memory (static-hardware) for values corresponding to 'nCk' combination of values from 0 to n-1.

Assuming 'n' as 6 and 'k' as 4, I need to store values (8 or 16 bit) corresponding to combinations:

(1,2,3,4) (1,2,3,5) (1,2,3,6) (1,2,4,5) (1,2,4,6) (1,2,5,6) (1,3,4,5) (1,3,4,6) (1,3,5,6) (1,4,5,6) (2,3,4,5) (2,3,4,6) (2,3,5,6) (2,4,5,6) (3,4,5,6)

Once I have the 'k' (4 here) digits, I should be able to directly access the element corresponding to the 'k' tuple.

Any lower index of the k tuple will be less than the higher indices and none of the indices are equal.

Is it possible to generate an addressing scheme to store and retrieve such data without searching? This needs to be done with minimum computation while address is generated and minimum amount of memory possible. (I think that some memory will be wasted irrespective of the method.)

I thought of linear hashing with different constants for different indices but that leads to a lot of memory loss or high computation complexity for calculating the constants.

Any suggestion regarding this problem will be of great help.

Example:

(combination -> corresponding value in memory)

([(1,2,3,4)->14], [(1,2,3,5)->3], [(1,2,3,6)->-4], [(1,2,4,5)->7], [(1,2,4,6)->22], [(1,2,5,6)->-11], [(1,3,4,5)->5], [(1,3,4,6)->3], [(1,3,5,6)->-1], [(1,4,5,6)->9], [(2,3,4,5)->35], [(2,3,4,6)->4], [(2,3,5,6)->7], [(2,4,5,6)->-2], [(3,4,5,6)->6])

If my input for the above module is (2,3,5,6) I should be able to directly get the value (7).

Edit: 'n' and 'k' are always even.

Answer 1

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 :

1. either the two value are both in the first part of the possible values (0 up to 7)
2. either they are both in the second part of the possible values (8 up to 15)
3. 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.