Сохранить перестановку с меньшим количеством байтов, чем длина перестановки - PullRequest
Новая
       15

Сохранить перестановку с меньшим количеством байтов, чем длина перестановки

0 голосов
/ 21 июня 2019

Я хочу сохранить перестановку длиной N менее чем N байтов. Перестановка длины N имеет элементы 1,2,3,....,N.

Перестановка имеет следующие предпочтения:

Дополнительное чтение: Ранговая и unrank перестановка со специальными свойствами

Есть ли способ объединить эти предпочтения, чтобы минимизировать возможные перестановки для ранжирования? Или есть больше предпочтений, которые можно использовать для описания перестановки в меньшем количестве байтов, чем в длинном?

Моя идея состояла в том, чтобы указать подмножество перестановок и затем ранжировать его, но я не смог объединить предпочтения, чтобы создать одно подмножество, определенное через предпочтения.

1 Ответ

1 голос
/ 21 июня 2019

В общем, нет.

Перестановки длины n только с одним циклом находятся в 1-1 соответствии с перестановками длины n-1.

Сила - это положительное целое число, которое не может превышать n^2.

Количество возможных цепочек битов 2^(n-1).

По принципу голубя, для некоторой цепочки битов и некоторой силы должно быть не менее (n-1)! / (2^(n-1) n^2) = n! / (2^(n-1) n^3).

Из приближения Стерлинга мы можем видеть, что 

log2( n! / (2^(n-1) n^3) )
    = n log2(n) - n log2(e) + O(log2(n)) - (n-1) - 3 log2(n)
    = n log2(n) - n (log2(e) + 1) - O(log2(n))
    = n log2(n) + O(n)

Что говорит нам о том, что количество необходимых битов, даже в ваших условиях, растет быстрее, чем линейное. Поэтому для достаточно большого n вам потребуется более 1022 * байтов данных, чтобы указать одну перестановку.

...