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 size1 slots, ar(1) = the number of size2 slots, etc.
For example, an object having 2x size3 slots and 1x size1 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

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 numberretr()
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