Fitting 20 values into 5 bits

I need to store 20 different values into 5 bits but I fail to find a good mapping function for that.

An object can have up to 3 slots, each slot having a size of 1, 2, or 3. The order does not matter.

This can be represented in 2 ways:

  • an array of length 3 where ar(0) = the size of slot #1, ar(1) = size of slot #2, etc. where a size of 0 means the slot is missing ;
  • because the order does not matter, an array of length 3 where ar(0) = the number of size-1 slots, ar(1) = the number of size-2 slots, etc.

For example, an object having 2x size-3 slots and 1x size-1 slot would be [3,3,1] using the first representation or [1,0,2] using the second representation.

Since the order doesn't matter, [3,3,1], [3,1,3], and [1,3,3] are the same (1st rep). That's a total of 20 combinations.

So far, I can map this to 6 bits using the following simple formula:

N = 13 * #slot3 + 4 * #slot2 + #slot1

With the given example, that would be 2*13 + 1 = 27.

Reversing is done with:

#slot3 = N / 13
#slot2 = (N % 13) / 4
#slot1 = (N % 13) % 4

As said before, that ranges from 0 (no slot at all) to 3*13=39 (3x slot3) with gaps which requires 6 bits.

How can I fit this into 5 bits without using a map or a big switch/case?

1 answer

  • answered 2018-11-08 10:40 MBo

    You have 20 ordered combinations of values 0,1,2,3 and want to find easy way of numbering these combinations and retrieving combinations by number.

    For combinations, sorted descending, there are 10 combinations starting from 3, 6 combinations starting from 2, 3 combinations starting from 1 and one zero combination. These values are "triangular numbers". At the second stage (second combination item) values 4,3,2,1 are involved ("linear numbers"). Seems you don't want hold them in a table, so all values might be calculated "on the fly".

    This is Python example of finding number of combination num() and retrieveing combination by number retr()

       def num(lst):
        lst.sort(reverse=True)
        n = 0
        j = 0
        for i in range(lst[0] + 1):
            j += i
            n += j
        for i in range(lst[1] + 1):
            n = n + i
        n = n + lst[2]
        return n
    
    def retr(num):
        result = []
        i = 0
        j = 1
        k = 1
        while num >= k:
            j += i
            k += j
            num -= k
            i += 1
        num += k - j
        result.append(i)
        i = 0
        while num > i:
            i += 1
            num -= i
        result.append(i)
        result.append(num)
        return result
    
    for i in range(20):
        comb = retr(i)
        print(comb, num(comb))
    
    [0, 0, 0] 0
    [1, 0, 0] 1
    [1, 1, 0] 2
    [1, 1, 1] 3
    [2, 0, 0] 4
    [2, 1, 0] 5
    [2, 1, 1] 6
    [2, 2, 0] 7
    [2, 2, 1] 8
    [2, 2, 2] 9
    [3, 0, 0] 10
    [3, 1, 0] 11
    [3, 1, 1] 12
    [3, 2, 0] 13
    [3, 2, 1] 14
    [3, 2, 2] 15
    [3, 3, 0] 16
    [3, 3, 1] 17
    [3, 3, 2] 18
    [3, 3, 3] 19