Подгонка 20 значений в 5 бит - PullRequest
Новая
       8

Подгонка 20 значений в 5 бит

0 голосов
/ 08 ноября 2018

Мне нужно хранить 20 различных значений в 5 битах, но я не могу найти для этого подходящую функцию отображения.

Объект может иметь до 3 слотов, каждый из которых имеет размер 1, 2 или 3. Порядок не имеет значения.

Это можно представить двумя способами:

  • массив длины 3, где ar (0) = размер слота № 1, ar (1) = размер слота № 2 и т. Д., Где размер 0 означает, что слот отсутствует;
  • поскольку порядок не имеет значения, массив длиной 3, где ar (0) = количество слотов размера 1, ar (1) = количество слотов размера 2 и т. Д.

Например, объект, имеющий 2x слота размера 3 и 1 слот размера 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 битов.

Как я могу вписать это в 5 бит без использования карты или большого переключателя / кейса?

1 Ответ

0 голосов
/ 08 ноября 2018

У вас есть 20 упорядоченных комбинаций значений 0,1,2,3 и вы хотите найти простой способ нумерации этих комбинаций и получения комбинаций по номеру.

Для комбинаций, отсортированных по убыванию, существует 10 комбинаций, начиная с 3, 6 комбинаций, начиная с 2, 3 комбинации, начиная с 1 и одной нулевой комбинации. Эти значения являются «треугольными числами». На втором этапе (второй комбинированный элемент) задействованы значения 4,3,2,1 («линейные числа»). Кажется, вы не хотите хранить их в таблице, поэтому все значения могут быть вычислены «на лету».

Это пример 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
...