algorithm - what - permutations without repetition

Dado el número lexicográfico de una permutación, es posible obtener cualquier artículo en O(1)

Question

Quiero saber si la tarea explicada a continuación es incluso teóricamente posible, y si es así cómo podría hacerlo.

Se le otorga un espacio de N elementos (es decir, todos los números entre 0 y N-1 ). Miremos el espacio de todas las permutaciones en ese espacio, y llámenlo S El i ésimo miembro de S , que puede marcarse S[i] , es la permutación con el número lexicográfico i .

Por ejemplo, si N es 3, entonces S es esta lista de permutaciones:

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

(Por supuesto, cuando se mira una gran N , este espacio se vuelve muy grande, N! Para ser exactos).

Ahora, ya sé cómo obtener la permutación por su número de índice i , y ya sé cómo hacer lo inverso (obtener el número lexicográfico de una permutación determinada). Pero quiero algo mejor.

Algunas permutaciones pueden ser enormes por sí mismas. Por ejemplo, si estás viendo N=10^20 . (El tamaño de S sería (10^20)! Que creo que es el número más grande que he mencionado en una pregunta de desbordamiento de pila :)

Si solo está mirando una permutación aleatoria en ese espacio, sería tan grande que no podría almacenar todo en su disco duro, y mucho menos calcular cada uno de los elementos por número lexicográfico. Lo que quiero es poder acceder a los elementos en esa permutación, y también obtener el índice de cada elemento. Es decir, dado que N e i especifican una permutación, tiene una función que toma un número de índice y encuentra el número que reside en ese índice, y otra función que toma un número y determina en qué índice reside. Quiero hacer eso en O(1) , así que no necesito almacenar o iterar sobre cada miembro en la permutación.

Loco, dices? ¿Imposible? Podría ser. Pero considere esto: un cifrado de bloque, como AES, es esencialmente una permutación, y casi logra las tareas que describí anteriormente. AES tiene un tamaño de bloque de 16 bytes, lo que significa que N es 256^16 que es alrededor de 10^38 . (El tamaño de S , no es que importe, es asombroso (256^16)! O alrededor de 10^85070591730234615865843651857942052838 , que bate mi reciente récord de "mayor número mencionado en Stack Overflow" :)

Cada clave de cifrado AES especifica una única permutación en N=256^16 . Esa permutación no podría almacenarse en su computadora, porque tiene más miembros que átomos en el sistema solar. Pero, le permite acceso al artículo. Al encriptar datos usando AES, está viendo el bloque de datos por bloque, y para cada bloque (miembro de range(N) ) saca el bloque encriptado, que es el miembro del range(N) que está en el número de índice de el bloque original en la permutación. Y cuando descifras, estás haciendo lo contrario (Encontrar el número de índice de un bloque). Creo que esto se hace en O(1) , no estoy seguro, pero en cualquier caso es muy rápido.

El problema con el uso de AES o cualquier otro cifrado de bloques es que te limita a N muy específico, y probablemente solo capte una pequeña fracción de las permutaciones posibles, mientras que yo quiero ser capaz de usar cualquier N I like y acceder a los elementos en cualquier permutación S[i] que me gusta.

¿Es posible obtener acceso al artículo O(1) en una permutación, dado el tamaño N y el número de permutación i ? ¿Si es así, cómo?

(Si tengo la suerte de obtener respuestas por código aquí, agradecería que estuvieran en Python).

ACTUALIZAR :

Algunas personas señalaron el triste hecho de que el número de permutación en sí mismo sería tan grande, que solo leer el número haría que la tarea no fuera factible. Luego, me gustaría revisar mi pregunta: dado el acceso a la representación fáctica del número lexicográfico de una permutación, ¿es posible obtener cualquier elemento en la permutación en O (lo más pequeño posible)?

Answer 1

Después de algunas investigaciones en Wikipedia , diseñé este algoritmo:

def getPick(fact_num_list):
"""fact_num_list should be a list with the factorial number representation,
getPick will return a tuple"""
result = [] #Desired pick
#This will hold all the numbers pickable; not actually a set, but a list
#instead
inputset = range(len(fact_num_list))
for fnl in fact_num_list:
result.append(inputset[fnl])
del inputset[fnl] #Make sure we can''t pick the number again
return tuple(result)

Obviamente, esto no alcanzará O (1) debido al factor que necesitamos para "elegir" cada número. Debido a que hacemos un bucle for y, suponiendo que todas las operaciones sean O (1), getPick se ejecutará en O (n).

Si necesitamos convertir de base 10 a base factorial, esta es una función auxiliar:

import math
def base10_baseFactorial(number):
"""Converts a base10 number into a factorial base number. Output is a list
for better handle of units over 36! (after using all 0-9 and A-Z)"""
loop = 1
#Make sure n! <= number
while math.factorial(loop) <= number:
loop += 1
result = []
if not math.factorial(loop) == number:
loop -= 1 #Prevent dividing over a smaller number than denominator
while loop > 0:
denominator = math.factorial(loop)
number, rem = divmod(number, denominator)
result.append(rem)
loop -= 1
result.append(0) #Don''t forget to divide to 0! as well!
return result

Nuevamente, esto se ejecutará en O (n) debido al while s.

Resumiendo todo, el mejor momento que podemos encontrar es O (n) .

PD: No soy un hablante nativo de inglés, por lo que pueden aparecer errores de ortografía y fraseo. Disculpas de antemano, y avíseme si no puede evitar algo.

Answer 2

El secreto para hacer esto es "contar en base factorial".

De la misma manera que 134 = 1 * 10 ^ 2 + 3 * 10 + 4, 134 = 5! + 2 * 3! + 2! => 10210 en notación factorial (¡incluye 1 !, excluye 0!). Si quieres representar a N !, necesitarás N ^ 2 dígitos base de diez. (Para cada dígito factorial N, el número máximo que puede contener es N). Hasta un poco de confusión acerca de lo que se llama 0, esta representación factorial es exactamente el número lexicográfico de una permutación.

Puedes usar esta idea para resolver el problema 24 de Euler a mano. Así que lo haré aquí, y verá cómo resolver su problema. Queremos la millonésima permutación de 0-9. En la representación factorial tomamos 1000000 => 26625122. Ahora para convertir eso a la permutación, tomo mis dígitos 0,1,2,3,4,5,6,7,8,9, y el primer número es 2, que es el tercero (podría ser 0), entonces selecciono 2 como el primer dígito, luego tengo una nueva lista 0,1,3,4,5,6,7,8,9 y tomo el séptimo número que es 8 etc, y obtengo 2783915604.

Sin embargo, esto supone que empiezas tu ordenamiento lexicográfico en 0, si realmente lo comienzas en uno, tienes que restar 1 de él, lo que da 2783915460. Que es, de hecho, la millonésima permutación de los números 0-9.

Obviamente, puede invertir este procedimiento y, por lo tanto, convertir fácilmente hacia atrás y hacia adelante entre el número lexiográfico y la permutación que representa.

No estoy del todo claro qué es lo que quiere hacer aquí, pero entender el procedimiento anterior debería ayudar. Por ejemplo, está claro que el número lexiográfico representa un orden que podría usarse como clave en una tabla hash. Y puede ordenar números comparando los dígitos de izquierda a derecha, así que una vez que haya insertado un número, nunca tendrá que trabajar fuera de él factorialmente.

Answer 3

Su pregunta es un poco discutible, porque su tamaño de entrada para un índice de permutación arbitraria tiene registro de tamaño (N!) (Suponiendo que quiera representar todas las permutaciones posibles) que es Theta (N log N), entonces si N es realmente grande, solo leer la entrada del índice de permutación tomaría demasiado tiempo, ciertamente mucho más que O (1). Es posible almacenar el índice de permutación de tal manera que si ya lo tenía almacenado, entonces podría acceder a los elementos en O (1) vez. Pero probablemente cualquier método sería equivalente a simplemente almacenar la permutación en la memoria contigua (que también tiene el tamaño Theta (N log N)), y si almacena la permutación directamente en la memoria, entonces la pregunta se vuelve trivial asumiendo que puede hacer O (1) ) acceso a la memoria. (Sin embargo, aún necesita tener en cuenta el tamaño de la codificación de bits del elemento, que es O (log N)).

En el espíritu de su analogía de encriptación, quizás deba especificar un pequeño SUBSET de permutaciones de acuerdo con alguna propiedad y preguntar si O (1) u O (log N) el acceso a los elementos es posible para ese pequeño subconjunto.

Answer 4

Todos los algoritmos correctos para acceder al k-ésimo elemento de una permutación almacenada en forma factorial deben leer los primeros k dígitos. Esto se debe a que, independientemente de los valores de los otros dígitos entre los primeros k, hace una diferencia si un dígito sin leer es un 0 o toma su valor máximo. Que este es el caso puede verse trazando el programa de decodificación canónico correcto en dos ejecuciones paralelas.

Por ejemplo, si queremos decodificar el tercer dígito de la permutación 1? 0, entonces para 100, ese dígito es 0, y para 110, ese dígito es 2.

Answer 5

Editar:

No entendí bien la pregunta, pero no fue un desperdicio. Mis algoritmos me permiten entender: la representación factorial del número lexicográfico de una permutación es casi la misma que la permutación misma. De hecho, el primer dígito de la representación fáctica es el mismo que el primer elemento de la permutación correspondiente (suponiendo que su espacio consiste en números del 0 al N-1). Sabiendo esto, no hay realmente un punto en el almacenamiento del índice en lugar de la permutación en sí. Para ver cómo convertir el número lexicográfico en una permutación, lea a continuación. Ver también este enlace de wikipedia sobre el código de Lehmer .

Publicación original:

En el espacio S hay N elementos que pueden llenar el primer espacio, lo que significa que hay (N-1)! elementos que comienzan con 0. Entonces i / (N-1)! es el primer elemento (vamos a llamarlo ''a''). El subconjunto de S que comienza con 0 consiste en (N-1)! elementos. Estas son las posibles permutaciones del conjunto N {a}. Ahora puede obtener el segundo elemento: es el i (% ((N-1)!) / (N-2)!). Repite el proceso y obtendrás la permutación.

Reverse es igual de simple. Comience con i = 0. Obtenga el segundo elemento de la permutación. Haz un conjunto de los dos últimos elementos y encuentra la posición del elemento en él (ya sea el 0º elemento o el 1º), vamos a llamar a esta posición j. Entonces i + = j * 2 !. Repite el proceso (puedes comenzar con el último elemento también, pero siempre será el 0º elemento de las posibilidades).

Código pesudo de Java-ish:

find_by_index(List N, int i){
String str = "";
for(int l = N.length-1; i >= 0; i--){
int pos = i/fact(l);
str += N.get(pos);
N.remove(pos);
i %= fact(l);
}
return str;
}
find_index(String str){
OrderedList N;
int i = 0;
for(int l = str.length-1; l >= 0; l--){
String item = str.charAt(l);
int pos = N.add(item);
i += pos*fact(str.length-l)
}
return i;
}

find_by_index debe ejecutarse en O (n) suponiendo que N está preordenado, mientras que find_index es O (n * log (n)) (donde n es el tamaño del espacio N)