Next Permutation

Q: ¿Cuál es la complejidad temporal de Next Permutation?

O(n) . Un recorrido desde la derecha encuentra el pivote, un segundo encuentra el valor con el que intercambiarlo y una inversión corrige el sufijo. La memoria adicional es O(1) , ya que todo ocurre dentro del arreglo.

MedioArrays y cadenas Dos punteros

+10

Recibes un arreglo de enteros nums, y los valores pueden repetirse. Imagina todos los arreglos distintos de estos valores, ordenados en orden lexicográfico: compara dos arreglos en el primer índice donde difieren, y el que tenga el valor menor en esa posición va primero. Devuelve el arreglo que viene justo después de nums en ese orden.

Si nums ya es el arreglo más grande, no hay ninguno después: devuelve el más pequeño, que es el de los valores ordenados en orden creciente. Intenta lograr un tiempo O(n) y usar O(1) de memoria adicional.

Función

nextPermutation(nums: integer-array) → integer-array

numsinteger-array: la disposición actual de los valores
Devuelveinteger-array: la siguiente disposición en orden lexicográfico, o los valores ordenados en orden creciente si nums es el mayor

Restricciones

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Ejemplos

Entrada: nums = [2, 5, 4, 1]
Salida: [4, 1, 2, 5]
Explicación: La cola 5, 4, 1 está disminuyendo, así que el 2 que la precede debe crecer. El menor valor de la cola mayor que 2 es 4; colócalo ahí y pon el resto en orden creciente: [4, 1, 2, 5].

Entrada: nums = [3, 2, 2, 1]
Salida: [1, 2, 2, 3]
Explicación: Todo el arreglo está descendiendo, así que es la disposición más grande de 3, 2, 2 y 1. La respuesta da la vuelta hasta llegar a la más pequeña, [1, 2, 2, 3].

Entrada: nums = [1, 5, 1]
Salida: [5, 1, 1]
Explicación: El primer 1 debe aumentar. El último 1 es igual a él, no mayor, así que el único valor que puede ocupar su lugar es 5, lo que da [5, 1, 1].

Para ir más allá

¿Cómo encontrarías, en cambio, la disposición anterior, la que va justo antes de nums en el orden lexicográfico?

Solución

Un sufijo descendente ya es tan grande como permiten sus valores, así que la siguiente disposición cambia el valor que está justo antes, el pivote. Aumenta el pivote en la menor cantidad posible y luego haz que el sufijo sea lo más pequeño posible. Para ello, se hacen dos recorridos desde la derecha y una inversión dentro del arreglo.

Organiza las listas en orden

Correcto, pero no termina con las pruebas más grandes

Intuición

Construye las permutaciones en profundidad a partir de los valores ordenados, probando siempre primero el menor valor sin usar. Así se generan en orden lexicográfico, por lo que la primera que sea estrictamente mayor que nums es la respuesta; si no hay ninguna, devuelve los valores ordenados. Los valores repetidos generan algunas permutaciones dos veces, como en 115, 151, 115, 151, 511, 511 para [1, 1, 5], pero una copia solo repite una permutación generada anteriormente, así que la primera mayor sigue siendo la siguiente.

La cantidad crece como n!: 12 valores distintos tienen 479,001,600 permutaciones.

Algoritmo

Ordena una copia de nums en pool.
Construye las disposiciones en profundidad, eligiendo las entradas no utilizadas de pool de izquierda a derecha.
Cuando una disposición esté completa, compárala con nums posición por posición.
Devuelve la primera disposición que sea mayor que nums.
Si ninguna es mayor, devuelve pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Encuentra el pivote, intercámbialo y revierte el sufijo

Intuición

El pivote es el primer valor desde la derecha que es menor que su vecino derecho: el 2 en [2, 5, 4, 1]. Es la posición más a la derecha que puede aumentar, y aumentar la posición más a la derecha posible mantiene el incremento al mínimo.

Intercambia el pivote con el valor más pequeño del sufijo que sea estrictamente mayor. El sufijo está en orden decreciente, así que ese es el valor más a la derecha que es mayor que el pivote: 4, lo que da [4, 5, 2, 1]. El sufijo sigue en orden decreciente, porque el pivote anterior encaja donde estaba el 4. Ahora que el inicio es mayor, el sufijo debe ser lo más pequeño posible, en orden creciente, y invertir una secuencia decreciente lo consigue: [4, 1, 2, 5].

Si no hay pivote, el arreglo está en su ordenamiento más grande, e invertirlo entero da el más pequeño. Cada paso es un recorrido o una inversión: tiempo O(n) y memoria O(1), aunque la versión en R devuelve una copia de O(n).

Algoritmo

Establece i en n-2 y muévelo hacia la izquierda mientras nums[i] ≥ nums[i + 1].
Si i ≥ 0, establece j en n-1 y muévelo hacia la izquierda mientras nums[j] ≤ nums[i]; después, intercambia nums[i] y nums[j].
Invierte la parte desde i + 1 hasta el final con dos índices que avanzan uno hacia el otro.
Devuelve nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Errores comunes y casos límite

Usar > en lugar de ≥ en la búsqueda del pivote. En [3, 2, 2, 1], el par 2, 2 no es un ascenso, y detenerse ahí elige un pivote que no puede crecer.
Intercambiar con un valor igual al pivote. En [1, 5, 1], intercambiar los dos 1 no cambia nada; busca un valor estrictamente mayor.
Intercambiar con el valor más grande del sufijo. En [2, 5, 4, 1], eso coloca el 5 al principio y omite todas las permutaciones que empiezan con 4.
Omitir el caso sin pivote. La permutación más grande debe volver ordenada, invirtiendo todo el arreglo.
En Rust, un índice usize que empieza en n-2 provoca un pánico cuando n = 1, y avanzar hacia la izquierda más allá de 0 provoca un pánico cuando no hay pivote. Usa un índice con signo o cuenta desde 1.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Next Permutation?

O(n). Un recorrido desde la derecha encuentra el pivote, un segundo encuentra el valor con el que intercambiarlo y una inversión corrige el sufijo. La memoria adicional es O(1), ya que todo ocurre dentro del arreglo.

¿Por qué inviertes el sufijo en lugar de ordenarlo?

Después del intercambio, el sufijo sigue siendo descendente, así que invertirlo ya lo ordena en orden creciente. Una inversión tarda O(n); una ordenación da el mismo resultado en O(n log n).

¿Next Permutation funciona con valores duplicados?

Sí, siempre que ambas comparaciones traten los valores iguales como no mayores. La búsqueda del pivote omite los vecinos iguales con ≥, y la búsqueda del intercambio omite los valores iguales al pivote con ≤. Después, [1, 5, 1] se convierte en [5, 1, 1], la siguiente disposición distinta.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

nums = [2, 5, 4, 1]

Salida Esperada

[4, 1, 2, 5]