¿Cómo generar una permutación?

Question

Mi pregunta es: se da una lista L de longitud n, y un número entero tal que 0 < = i < n !, cómo se puede escribir una función permanente (L, n) para producir la i-permutación de L en O (n) tiempo? Lo que quiero decir con ITH permutación es simplemente la permutación i en algún orden definido aplicación que deben tener las propiedades:

1. Para cualquier i y cualquier 2 listas A y B, Perm (a, i) y Perm (B , i) ambos deben asignar el elemento j-ésimo de A y B a un elemento en la misma posición para A y B.

2. Para cualquier entrada (A, i), (A, i) permanente (A, i)) == perm (A, j) si y solo si i == j.

NOTA: esto no es tarea. De hecho, resolví esto hace 2 años, pero olvidé por completo cómo, y me está matando. Además, aquí es un intento rota que hice en una solución:

def perm(s, i): 
    n = len(s) 
    perm = [0]*n 
    itCount = 0 
    for elem in s: 
    perm[i%n + itCount] = elem 
    i = i/n 
    n -= 1 
    itCount+=1 
    return perm 

también NOTA: el O (n) requisito es muy importante. De lo contrario, podría generar el n! lista de todas las permutaciones y solo devuelve su i-ésimo elemento.

Answer 1

def perm(sequence, index): 
    sequence = list(sequence) 
    result = [] 
    for x in xrange(len(sequence)): 
     idx = index % len(sequence) 
     index /= len(sequence) 
     result.append(sequence[idx]) 
     # constant time non-order preserving removal 
     sequence[idx] = sequence[-1] 
     del sequence[-1] 
    return result 

basado en el algoritmo para barajar, pero tomamos la parte menos significativa del número cada vez para decidir qué elemento a tener en lugar de un número aleatorio. Alternativamente, considéralo como el problema de convertir a una base arbitraria, excepto que el nombre base se reduce para cada dígito adicional.

Answer 2

¿Podría usar factoradics? Puede encontrar una ilustración a través de este MSDN article.

Actualización: Escribí un extension of the MSDN algorithm que encuentra la permutación de n cosas tomadas a la vez, incluso si n! = R.

Answer 3

Entonces, creo que finalmente lo resolví. Antes de leer cualquier respuesta, publicaré la mía aquí.

def perm(L, i): 
    n = len(L) 
    if (n == 1): 
    return L 
    else: 
    split = i%n 
    return [L[split]] + perm(L[:split] + L[split+1:], i/n) 

Answer 4

Hay n! permutaciones. El primer personaje se puede elegir de L de n maneras. ¡Cada una de esas elecciones se va (n-1)! permutaciones entre ellos. Entonces esta idea es suficiente para establecer un orden. En general, descubrirá en qué parte se encuentra, elija el elemento apropiado y luego recurse/loop en el menor L.

El argumento de que esto funciona correctamente es por inducción en la longitud de la secuencia. (boceto) Para una longitud de 1, es trivial. Para una longitud de n, utilice la observación anterior para dividir el problema en n partes, cada una con una pregunta en una L 'con longitud (n-1). Por inducción, todas las L's se construyen correctamente (y en tiempo lineal). Entonces está claro que podemos usar el IH para construir una solución para la longitud n.

Answer 5

Un enfoque computacional minimalista (escrito en pseudocódigo de estilo C):

function perm(list,i){ 
    for(a=list.length;a;a--){ 
     list.switch(a-1,i mod a); 
     i=i/a; 
    } 
    return list; 
} 

Nota que las implementaciones que dependen de la eliminación de elementos de la lista original tienden a darse en O (n^2) el tiempo, en el mejor de O (n * log (n)) dada una implementación de lista de estilo de árbol especial diseñada para insertar y eliminar elementos de lista rápidamente.

El código anterior, en lugar de reducir la lista original y mantenerla en orden solo mueve un elemento desde el final a la ubicación vacante, sigue haciendo una correspondencia perfecta 1: 1 entre índice y permutación, solo un poco más codificado, pero en tiempo O (n) puro.