Я хочу знать, возможна ли теоретически описанная ниже задача, и если да, то как я могу это сделать.

Вам дано местоN элементы (то есть все числа между0 а такжеN-1.) Давайте посмотрим на пространство всех перестановок в этом пространстве, и назовем егоS,iчленS, который можно отметитьS[i], - перестановка с лексикографическим числомi.

Например, еслиN 3, тоS этот список перестановок:

S[0]: 0, 1, 2
S[1]: 0, 2, 1
S[2]: 1, 0, 2
S[3]: 1, 2, 0
S[4]: 2, 0, 1
S[5]: 2, 1, 0

(Конечно, при взгляде на большойN, это пространство становится очень большим,N! если быть точным.)

Теперь я уже знаюкак получить перестановку по ее номеруi, и я уже знаю, как сделать обратное (получить лексикографический номер данной перестановки.) Но я хочу что-то лучше.

Некоторые перестановки могут быть огромными сами по себе. Например, если вы смотрите наN=10^20, (РазмерS было бы(10^20)! который я считаю самым большим числом, которое я когда-либо упоминал в вопросе переполнения стека :)

Если вы смотрите на случайную перестановку в этом пространстве, она будет настолько большой, что вы не сможете сохранить все это на своем жестком диске, не говоря уже о том, чтобы рассчитать каждый из элементов по лексикографическому номеру. Я хочу иметь возможность доступа к элементам на этой перестановке, а также получить индекс каждого элемента. То есть даноN а такжеi чтобы задать перестановку, нужно иметь одну функцию, которая принимает индексный номер и найти номер, который находится в этом индексе, и другую функцию, которая принимает номер и находит, в каком индексе он находится. Я хочу сделать это вO(1), поэтому мне не нужно хранить или перебирать каждый элемент в перестановке.

Сумасшедший, говорите? Невозможно? Это может быть. Но учтите следующее: блочный шифр, такой как AES, по сути является перестановкой, и он почти выполняет задачи, которые я изложил выше. AES имеет размер блока 16 байтов, что означает, чтоN является256^16 который вокруг10^38, (РазмерSне то, что это имеет значение, это ошеломляющий(256^16)!или около10^85070591730234615865843651857942052838, который превосходит мой недавний рекорд по «наибольшему числу, упомянутому в переполнении стека» :)

Каждый ключ шифрования AES определяет одну перестановку наN=256^16, Эту перестановку невозможно сохранить целиком на вашем компьютере, потому что в ней больше членов, чем атомов в Солнечной системе. Но это позволяет вам получить доступ к элементу. Зашифровывая данные с помощью AES, вы смотрите на блок данных за блоком и для каждого блока (членаrange(N)) вы выводите зашифрованный блок, членом которого являетсяrange(N) то есть в номер индекса исходного блока в перестановке. А когда вы расшифровываете, вы делаете обратное (Нахождение индексного номера блока.) Я считаю, что это делается вO(1)Я не уверен, но в любом случае это очень быстро.

Проблема с использованием AES или любого другого блочного шифра состоит в том, что он ограничивает васNи это, вероятно, только захватывает крошечную долю возможных перестановок, в то время как я хочу иметь возможность использовать любыеN Я люблю и делаю доступ к элементу на любой перестановкеS[i] это мне нравится.

Можно ли получитьO(1) доступ к элементу по перестановке, заданный размерN и номер перестановкиi? Если так, то как?

(Если мне посчастливится получить здесь ответы на вопросы по коду, буду признателен, если они будут в Python.)

ОБНОВИТЬ:

Некоторые люди указали на печальный факт, что само число перестановок было бы настолько огромным, что простое чтение числа сделало бы задачу невыполнимой. Затем я хотел бы пересмотреть мой вопрос:Предоставленный доступ кфактическое представление из лексикографического числа перестановки, возможно ли получить какой-либо элемент в перестановке в O (как можно меньше)?