Permutations

+10

Recibes una lista nums de enteros distintos. Devuelve todos los ordenamientos de esos valores, cada uno como una lista que usa cada valor exactamente una vez, de modo que n valores den n! ordenamientos. Enuméralos en orden lexicográfico: compara dos ordenamientos posición por posición y deja que decida la primera diferencia. Para [1, 2, 3], eso pone [1, 2, 3] primero y [3, 2, 1] al final.

Función

permute(nums: integer-array) → integer-2d-array

numsinteger-array: los valores, todos diferentes, en cualquier orden
Devuelveinteger-2d-array: cada ordenación de los valores, enumeradas en orden lexicográfico

Restricciones

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
Todos los valores de nums son diferentes.
nums puede venir en cualquier orden.

Ejemplos

Entrada: nums = [3, 1, 2]
Salida: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explicación: Tres valores tienen 3! = 6 ordenaciones. Ordenados, los valores son 1, 2, 3, así que primero van las ordenaciones que empiezan con 1, y [1, 2, 3] va antes que [1, 3, 2] porque 2 es menor que 3 en la segunda posición. El orden de entrada no importa.

Entrada: nums = [2, -1]
Salida: [[-1, 2], [2, -1]]
Explicación: Dos valores se pueden escribir en dos órdenes. [-1, 2] va primero porque -1 es menor que 2.

+13 pruebas ocultas al enviar

Para ir más allá

Dado un ordenamiento, ¿puedes producir el siguiente en orden lexicográfico in situ, en O(n) tiempo y con O(1) espacio adicional?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una lista de n valores diferentes tiene n! ordenamientos, 720 para seis valores, y la respuesta debe enumerarlos todos, así que el trabajo es de al menos n × n!. El desafío es construir cada ordenamiento una vez y generarlos en orden lexicográfico. Recorrer los valores ordenados mediante retroceso, probando siempre primero el valor no utilizado más pequeño, permite hacer ambas cosas a la vez.

Inserta en cada espacio y luego ordénalos

Intuición

Construye las ordenaciones de un valor a la vez. Sin valores, hay una ordenación: la lista vacía. Para añadir el valor 3 a la ordenación [1, 2], colócalo en cada uno de sus tres espacios: [3, 1, 2], [1, 3, 2] y [1, 2, 3]. Hazlo con cada ordenación que tengas, y las ordenaciones de k valores se convierten en las ordenaciones de k+1 valores.

Cada ordenación de k+1 valores se construye exactamente una vez: saca de ella el valor más reciente y obtendrás la ordenación de la que surgió, mientras que la posición del valor más reciente indica el espacio. Así, las cantidades son 1, 2, 6, 24, y n valores dan n! ordenaciones.

No aparecen en el orden requerido. Para [1, 2, 3], la primera ordenación que se construye es [3, 2, 1], así que al final se ordena comparando posición por posición. Esa ordenación es la parte costosa: n! ordenaciones requieren alrededor de n! × log(n!) comparaciones, y cada una lee hasta n valores. Para seis valores, son aproximadamente 720 × 9.5 × 6, unas 41,000 lecturas. El método también mantiene en memoria toda una generación de ordenaciones mientras construye la siguiente.

Algoritmo

Empieza con una lista que contenga un orden vacío.
Para cada valor de nums, crea una lista nueva: para cada orden existente y cada espacio desde 0 hasta su longitud, copia el orden con el valor insertado en ese espacio.
Reemplaza la lista anterior por la nueva.
Ordena los órdenes posición por posición y devuélvelos.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

Retroceso con un array de elementos usados

Intuición

Rellena n espacios de izquierda a derecha. El primer espacio tiene n candidatos, el segundo n-1, y así sucesivamente; de ahí viene n!. Dibuja esas elecciones como un árbol: la raíz es un camino vacío, cada arista coloca un valor más y cada hoja, a profundidad n, es un ordenamiento completo. Para los valores ordenados 1, 2, 3, la raíz tiene los hijos [1], [2] y [3]; [1] tiene los hijos [1, 2] y [1, 3]; cada uno de ellos tiene una hoja.

El retroceso recorre este árbol con un único path compartido y una marca used por cada valor. En cada nodo, recorre los valores y omite los que ya están marcados. Para cada valor disponible, lo elige (lo marca como usado y lo añade), lo explora (llama recursivamente un nivel más abajo) y luego lo deselige (lo elimina y lo marca como disponible). El paso de deselección restaura exactamente el estado que tenía el bucle antes, así que el siguiente valor se prueba desde el mismo nodo. Un camino de longitud n es una hoja: registra una copia y retorna.

El orden se obtiene automáticamente. El bucle prueba primero el menor valor disponible, y el recorrido termina todos los ordenamientos que empiezan con un prefijo dado antes de cambiar ese prefijo. Así que todos los ordenamientos que empiezan con 1 aparecen antes que cualquiera que empiece con 2, y entre ellos [1, 2, ...] aparece antes que [1, 3, ...]. Ese es el orden lexicográfico. Por eso también ordenas nums primero: el bucle recorre los índices, así que estos deben estar ordenados por valor.

El árbol tiene aproximadamente e × n! nodos (e es aproximadamente 2.72), y cada uno ejecuta un bucle de n elementos, así que el tiempo es O(n × n!), el mismo orden que el tamaño de la respuesta. Aparte de la salida, el camino, las marcas y la pila de llamadas contienen como máximo n elementos cada uno.

Algoritmo

Ordena los valores y crea un arreglo used de n indicadores false.
Escribe explore(). Si path contiene n valores, añade una copia al resultado y retorna.
De lo contrario, para cada índice i de 0 a n-1 cuyo valor esté libre: márcalo como usado y añade values[i] (elige), llama a explore() (explora), luego elimínalo y márcalo como libre (deselige).
Llama a explore() una vez y retorna el resultado.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

Errores comunes y casos límite

Los errores de retroceso casi siempre se deben a un estado que no se restaura o que se comparte por accidente.

Registrar path en lugar de una copia. Las n! entradas terminan siendo la misma lista, que queda vacía cuando termina el recorrido.
Deshacer solo la mitad de una elección. Si eliminas el valor, pero dejas establecido used[i], ese valor no vuelve a aparecer en ninguna rama posterior y obtienes menos de n! ordenaciones.
No ordenar nums primero. El recorrido sigue encontrando todas las ordenaciones, pero las devuelve siguiendo el orden de entrada, así que la entrada [3, 1, 2] aparecería primero.
Usar el método de intercambio (intercambiar nums[start] con cada posición posterior, recurrir y volver a intercambiar) sin una ordenación final. Encuentra las n! ordenaciones, pero para [1, 2, 3] devuelve [3, 2, 1] antes que [3, 1, 2].
Comprobar si un valor ya se usó buscándolo en path. Aquí solo funciona porque los valores son distintos y cuesta n en cada paso. Una marca por índice es O(1) y sigue funcionando cuando se repiten los valores.

Preguntas frecuentes4

¿Cuántas permutaciones tiene una lista de n elementos distintos?

n!, se lee n factorial: n opciones para la primera posición, n-1 para la segunda, hasta llegar a una para la última; todas multiplicadas. Tres valores dan 6 ordenaciones, seis dan 720 y diez ya dan 3,628,800, por eso los problemas de permutaciones mantienen n pequeño.

¿Cuál es la complejidad temporal de generar todas las permutaciones?

O(n × n!). Hay n! ordenaciones y escribir cada una requiere n pasos, así que ningún método puede hacerlo mejor si tiene que devolverlas todas. El retroceso alcanza este límite y, además de la salida, necesita O(n) de espacio para la ruta actual, las marcas de elementos usados y la recursión.

¿Por qué el retroceso genera permutaciones en orden lexicográfico?

Es un recorrido en profundidad que prueba primero el valor disponible más pequeño. Termina todos los ordenamientos que empiezan con un prefijo determinado antes de pasar al siguiente prefijo, y prueba los prefijos de menor a mayor. Esto coincide con la forma en que un diccionario ordena las palabras, siempre que la entrada se ordene antes de iniciar el recorrido.

¿Cómo generas permutaciones cuando la entrada tiene duplicados?

Ordena los valores y, en cada posición, omite un valor que sea igual al anterior mientras esa copia anterior no esté en uso: i > 0, values[i] == values[i-1] y !used[i-1]. Eso obliga a colocar los valores iguales en su orden original, de modo que cada orden distinto se construya una sola vez.

Python

def permute(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [3, 1, 2]

Esperado

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]