Кодировать и генерировать фиксированную последовательность уникальных чисел ниже N

Question

Можно создать произвольную последовательность чисел, используя часть (можно использовать все) чисел в диапазоне от 0 до 2^n-1. Давайте рассмотрим последовательности, в которых все числа уникальны.

Например, если n = 4, некоторые последовательности:

4 2 5 7 11 3
15 1 6
6 5 8 2 3 10 12 13 4

Вопрос: Можно ли сгенерировать такую ​​последовательность без использования памяти для хранения всей последовательности?

Я имею в виду какую-то функцию F, которая выполняет только битовые манипуляции и дает следующее число, используя предыдущее. Например, в последовательности 7 3 5 9: F(7)=3, F(3)=5, F(5)=9.

Как построить такую ​​функцию F, если я заранее знаю последовательность?

Answer 1

Нет, не в общем. Хотя последовательность S не обязательно должна быть представлена ​​буквально в памяти, чтобы мы могли реализовать генерирующую функцию F, любая функция F эффективно кодирует последовательность S, и, следовательно, требуется память.

(Генерирующая функция F - это такая функция, что F (i), где i является элементом последовательности, является следующим элементом последовательности или, если i является последним элементом, является некоторым значением, указывающим на это.)

Конечно, возможно, что некоторые последовательности, такие как тривиальные 0, 1, 2, 3,…, могут быть сгенерированы небольшими функциями. Однако рассмотрим некоторое количество битов b. Число различных функций, которые могут быть закодированы с помощью b битов, составляет не более 2 ^b (с использованием любой схемы кодирования, которую вы пожелаете - исходного кода, машинного кода, абстрактного математического представления и т. Д.). Количество различных последовательностей составляет 2 ⁿ !, поэтому необходимо количество различных генерирующих функций 2 ⁿ !.

Следовательно, 2 ^b ≥ 2 ⁿ !, поэтому b ≥ log ₂ (2 ⁿ !). Таким образом, если мы хотим иметь достаточно памяти для хранения генерирующей функции для любой последовательности в течение 2 ⁿ , нам нужно по крайней мере log ₂ (2 ⁿ !) бит.

Answer 2

Да, это так. Шифрование - это биекция между открытым текстом и шифротекстом. Каждый ввод открытого текста приводит к уникальному выводу зашифрованного текста, который затем может быть уникальным образом расшифрован до исходного открытого текста.

Для чисел проще всего использовать блочный шифр, такой как DES (64 бит) или AES (128 бит). Возможны другие размеры блока.

Для заданной последовательности вам необходимо сохранить шифровальный ключ, обычно такой же большой, как размер блока, и позицию, которой вы достигли во вводе открытого текста. Просто зашифруйте целые числа 0, 1, 2, 3, ... по порядку. Вывод будет серией неповторяющихся чисел в пределах данного размера блока. Чтобы сгенерировать больше чисел в той же последовательности, продолжайте с последнего использованного числа. Для другой последовательности измените ключ и начните снова с 0. Каждый ключ определяет перестановку возможных блоков данного размера.

Для последовательности, допускающей повторы, используйте хеш-функцию вместо шифра, хэширование 0, 1, 2, 3 и т. Д. Для различных последовательностей используйте блок XOR в качестве эквивалента ключа и XOR его с помощью ввода до хеширования. Вам нужно будет отслеживать позицию ввода, которую вы достигли, если вы хотите добавить к существующей последовательности.