将 20 个值拟合成 5 位

Question

我需要将 20 个不同的值存储到 5 位中，但我找不到合适的映射函数。

一个对象最多可以有 3 个槽，每个槽的大小为 1、2 或 3。顺序无关紧要。

这可以用两种方式表示：

长度为 3 的数组，其中 ar(0) = 插槽 #1 的大小，ar(1) = 插槽 #2 的大小，等等。其中大小为 0 表示缺少插槽；
因为顺序无关紧要，长度为 3 的数组，其中 ar(0) = size-1 槽的数量，ar(1) = size-2 槽的数量，等等

例如，具有 2x size-3 插槽和 1x size-1 插槽的对象将是 [3,3,1] 使用第一个表示或 [1,0,2] 使用第二个表示。

由于顺序无关紧要，因此 [3,3,1]、[3,1,3] 和 [1,3,3] 相同（第 1 次）。总共有20种组合。

到目前为止，我可以使用以下简单公式将其映射到 6 位：

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

对于给定的示例，这将是 2*13 + 1 = 27。

反转完成：

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

如前所述，范围从 0（根本没有插槽）到 3*13=39（3x 插槽 3），间隙需要 6 位。

如何在不使用地图或大 switch/case 的情况下将其放入 5 位？

Answer 1

您有 20 个值 0、1、2、3 的有序组合，并且想要找到对这些组合进行编号并按编号检索组合的简便方法。

组合方面，降序排列，从3开始有10个组合，从2开始有6个组合，从1开始有3个组合，还有1个零组合。这些值为 "triangular numbers"。在第二阶段（第二个组合项）涉及值 4,3,2,1 ("linear numbers")。似乎您不想将它们保存在 table 中，因此可能会计算所有值 "on the fly".

这是 Python 查找组合数 num() 和按数字检索组合的示例 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

将 20 个值拟合成 5 位

Fitting 20 values into 5 bits

math

binary-data