Сколько бит нужно для записи порядка 32 элементов?

Рейтинг: 3Ответов: 1Опубликовано: 13.04.2015

Есть исходный порядок 32 элементов: 0,1,2...31

Их перемешали. Нужен способ записать их новый порядок, занимающий минимум объёма.

Совсем в лоб: по 5 бит для каждого элемента = 160 бит (20 байт).

Некруто. С каждой «установленной» позицией, число вариантов для оставшихся сокращается. Последнему эл-ту вообще не нужно указывать позицию: осталось одно «парковочное место».

Нулевому эл-ту надо все 5 бит, чтобы обозначить одну из 32 позиций. Следующему (первому) – из 31, но то же 5 бит, хотя уже появился избыток в один вариант. Так до 15-го: 16*5. Дальше из 16 позиций выбираем – достаточно 4 бит. 16-23: 8*4 бит. Дальше из 8: 4*3 бит. Потом 2*2 и 1. Итого 16*5 + 8*4 + 4*3 + 2*2 + 1*1 + 0*0 = 129 бит

А может, есть более оптимальный вариант, сводящий к нулю избыточность записи?

алгоритм комбинаторика
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Всего возможно 32! новых порядков. Их можно перенумеровать (например, так), и каждую из перестановок идентифицировать её номером.

Итого нужно ceil(log_2 (32!)) бит. (Калькулятор вроде бы говорит, 118.) Это, по идее, теоретический минимум.