2

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.

Maximus
  • 143
  • 3
  • 12
  • Ok, so you need a mapping from k into what address range? Mapping for your example: k=0 -> 0, k=1 -> 1, ..., k=15 -> 15 is fine? – Adam Stelmaszczyk Jan 20 '14 at 19:06
  • Suppose 'n' is 10, nCk is max when k=5 so we need nCk addresses. I dont think it is possible to limit it to this exact value without much computation to find the address. I want to keep the computation minimum. 'n' can be atmax 16 which gives maximum of 16C8 memory locations. I think this clears your question – Maximus Jan 20 '14 at 19:11
  • Sorry, I don't understand. Could you please add a full example to your question? With input and desired output. – Adam Stelmaszczyk Jan 20 '14 at 19:14
  • Basically what I need is a 'k-D' addressing scheme where I do not use locations with higher indices smaller than lower indices.(like upper triangle in a 2-D matrix) – Maximus Jan 20 '14 at 19:14
  • So if I understand it correctly, you have a worst case of using `pow(2, ceil(log2(n)) * k)` addresses (addressing with a plain old vector) and a best case of using nCk addresses (but then you can't easily compute an address), and you want some other trade-off in between? – harold Jan 20 '14 at 19:29
  • @harold Yes sir. The best case is exactly as you said. But the worst case is pow(2, ceil(log2(n-k)) * k). The 'n-k' comes into picture instead of 'n' because any value of a given index wont take more than 'n-k' values as higher index value is always higher than lower index value (like an upper triangle in case of 2-D). Keeping every otehr index constant, a given index can be moved 'n-k' places at max and there are k such indices. There can be some tradeoff in case of memory, but addressing logic cannot be much complex – Maximus Jan 20 '14 at 19:39

1 Answers1

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.

Bruno JJE
  • 231
  • 2
  • 6
  • Thank you sir, this really helps. Can you suggest a method to reduce the memory requirement if 'n' and 'k' are always **even**. I prefer the 1st proposition , as in this way I can store all the 'nCk' combination with constant 'n' and variable 'k' taking all even values less than 'n'. Here half of the memory is unused. Is it possible to minimize this if you don't need to compute for odd values of 'l' – Maximus Jan 21 '14 at 06:58