i-th elemento de permutación k-th

¿Hay un algoritmo rápido para calcular el elemento i-th (0 <= i < n) de la permutación k-th (0 <= k < n!) la secuencia 0..n-1?

Se puede elegir cualquier orden de permutaciones, no tiene que ser lexicográfico. Hay algoritmos que construyen la permutación k -th en O(n) (ver más abajo). Pero aquí no se necesita la permutación completa, solo su elemento i -th. ¿Hay algoritmos que pueden funcionar mejor que O(n) ?

¿Hay un algoritmo que tenga una complejidad de espacio menor que O (n)?

Hay algoritmos que construyen la permutación k -th al trabajar en una matriz de tamaño n (ver más abajo), pero los requisitos de espacio pueden ser indeseables para n grande. ¿Hay algún algoritmo que necesite menos espacio, especialmente cuando solo se necesita el elemento i -th?


Algoritmo que construye la k -ésima permutación de la secuencia 0..n-1 con una complejidad de tiempo y espacio de O(n) :

 def kth_permutation(n, k): p = range(n) while n > 0: p[n - 1], p[k % n] = p[k % n], p[n - 1] k /= n n -= 1 return p 

Fuente: http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Probablemente no pueda obtener el dígito i de la permutación en k de n elementos en O (n) tiempo o espacio, porque representar el número k requiere O (registro (n!)) = O (n registro n) bits , y cualquier manipulación con él tiene la complejidad del tiempo correspondiente.

Lo que jkff dijo. Puede modificar un algoritmo como el que publicó para devolver el elemento i-th de la permutación k-th, pero no ahorrará mucho tiempo (o espacio), y ciertamente no reducirá la complejidad de Big-O del algoritmo básico.

El código de permutación desordenado que usted publicó no es realmente susceptible de modificación porque tiene que recorrer todos los elementos que realizan sus intercambios, y es doloroso determinar si es posible salir del ciclo antes de tiempo.

Sin embargo, hay un algoritmo similar que produce permutaciones ordenadas, y es posible romperlo antes, pero aún es necesario realizar i bucles internos para obtener el elemento i-th de la permutación k-th.

He implementado este algoritmo como clase, solo para mantener ordenadas las diversas constantes que usa. El código a continuación produce permutaciones completas, pero debería ser fácil de modificar para devolver simplemente el elemento i-th.

 #!/usr/bin/env python ''' Ordered permutations using factorial base counting Written by PM 2Ring 2015.02.15 Derived from C code written 2003.02.13 ''' from math import factorial class Permuter(object): ''' A class for making ordered permutations, one by one ''' def __init__(self, seq): self.seq = list(seq) self.size = len(seq) self.base = factorial(self.size - 1) self.fac = self.size * self.base def perm(self, k): ''' Build kth ordered permutation of seq ''' seq = self.seq[:] p = [] base = self.base for j in xrange(self.size - 1, 0, -1): q, k = divmod(k, base) p.append(seq.pop(q)) base //= j p.append(seq[0]) return p def test(seq): permuter = Permuter(seq) for k in xrange(permuter.fac): print '%2d: %s' % (k, ''.join(permuter.perm(k))) if __name__ == '__main__': test('abcd') 

Este algoritmo tiene un poco más de sobrecarga que el creador de permutaciones no ordenado: requiere que el factorial se calcule por adelantado y, por supuesto, el factorial se vuelve muy grande muy rápidamente. Además, requiere una división extra por bucle interno. Por lo tanto, el ahorro de tiempo en rescatar el bucle interno una vez que haya encontrado el elemento i-th puede ser compensado por estas sobrecargas.


FWIW, el código en su pregunta tiene margen de mejora. En particular, k /= n debe escribirse como k //= n para garantizar que se use la división entera; su código funciona bien en Python 2 pero no en Python 3. Sin embargo, dado que necesitamos tanto el cociente como el rest, tiene sentido utilizar la función incorporada divmod() . Además, al reorganizar un poco las cosas podemos evitar los cálculos múltiples de n - 1

 #!/usr/bin/env python def kth_permutation(n, k): p = range(n) while n: k, j = divmod(k, n) n -= 1 p[n], p[j] = p[j], p[n] return p def test(n): last = range(n) k = 0 while True: p = kth_permutation(n, k) print k, p if p == last: break k += 1 test(3) 

salida

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