Siguiente permutación mayor

(26 de noviembre de 2020)

Permutación de tres colores diferentes

Primero entendamos qué significa permutación. La definición tomada de Wikipedia dice: « En matemáticas , una permutación de una set es, en términos generales, una disposición de sus miembros en una secuencia o orden lineal , o si el conjunto ya está ordenado , una reordenación de sus elementos. La palabra «permutación» también se refiere al acto o proceso de cambiar el orden lineal de un conjunto ordenado. «

Entonces, como dice la definición, permutación significa reorganizar un conjunto de objetos dados en todos los pedidos posibles. Como podemos ver en el diagrama anterior, se pueden organizar tres colores diferentes de 6 formas, es decir, {RGB, RBG, GRB, GBR, BRG, BGR}.

Una fórmula matemática para calcular el número de arreglos posibles para n objetos diferentes viene dado por n !, donde n! = n * (n-1) * (n-2) *… * 1

Hay muchas formas de generar sistemáticamente todas las permutaciones de una secuencia dada. Un algoritmo clásico se basa en encontrar la siguiente permutación en orden lexicográfico / diccionario / alfabético, si existe.

Entonces, el enunciado del problema aquí es que se nos da un conjunto de alfabetos, tal vez podamos llámelo cadena, y tenemos que encontrar el siguiente conjunto lexicográfico de alfabetos o la siguiente cadena lexicográfica mayor o la cadena que vendrá a continuación en el diccionario después de la cadena actual que tenga el mismo conjunto de alfabetos que en la cadena actual.

Tomemos un ejemplo de números para comprender mejor.

Número = [4,5,2,6,7,3,1]
El siguiente número mayor será = [4,5,2, 7,1,3,6 ]

Fuerza bruta

Lo primero que nos vendrá a la mente es encontrar todas las permutaciones del número dado y la más pequeña de esas permutaciones que también sea mayor que nuestro número actual será nuestra respuesta. Como vimos anteriormente, hay n! posibilidades (n = número de dígitos en el número), considerando todos los dígitos como distintos, por lo que si continuamos encontrando todas las permutaciones para un número dado, tomará O (n!) tiempo para calcular. Eso es una gran complejidad de tiempo si la n es un número grande.

Optimización

Tenemos que pensar cómo podemos mejorar esto. Si observamos con atención, tal vez para un conjunto más pequeño de números, podríamos ver patrones. Probemos con algunos ejemplos:

[2,1,3] = el siguiente número mayor es 231
[1,1,5] = el siguiente número mayor es 151
[2,3 , 5,4] = el siguiente número mayor es 2435
[3,2,1] = no podemos formar un número mayor que el número actual a partir de todas las posibles permutaciones

Conclusiones de lo anterior observación:

Caso 1: [3,2,1]

Aquí comenzamos a movernos desde el extremo derecho e intentamos encontrar el primer elemento decreciente, de modo que podamos reemplazarlo con el elemento mayor que él mismo desde el lado derecho.

Caso 1: el siguiente elemento mayor no es posible en secuencia no creciente

Caso 2: [2,3,5,4]

index = 1, índice para el primer elemento decreciente desde el extremo derecho
busque el siguiente elemento más grande mayor que 3 en el lado derecho de i = 1, cámbielo por nums [i]
Ahora, ordena los elementos restantes después de i = 1 en orden ascendente para hacer el elemento más pequeño, podemos simplemente invertir los elementos después de i = 1 ya que ya están ordenados en el orden no creciente

Este gráfico demuestra que al intercambiar 4 y 5, la secuencia que comienza en 8, es decir, 86432 todavía está ordenada en orden no creciente y es bastante obvio ya que estamos reemplazando el primer elemento decreciente con el elemento que es más grande que él. y por lo tanto manteniendo el orden no creciente.

Una observación más que podemos tomar desde aquí es que, mientras buscamos el siguiente elemento más grande desde el índice j = i + 1 a la derecha, podemos detener la búsqueda en el índice j cuando nums [j] se vuelve menor o igual que nums [i], ya que los elementos posteriores a ese índice nunca pueden b e mayor que nums [i].

Fragmento de código

En el siguiente código, en caso de que el siguiente mayor la permutación no es posible, la estoy convirtiendo en la permutación más pequeña posible

Análisis de complejidad

Complejidad de tiempo = O (n) { para encontrar el primer elemento decreciente en el peor de los casos, p. ej. [1,5,4,3,2]} + O (n) {para encontrar el siguiente número mayor en el subarreglo restante a la derecha} + O (1) {para intercambiar el primer elemento decreciente con el siguiente elemento más grande} + O (n / 2) {para invertir la submatriz de i + 1 a len para ordenar en orden ascendente} = O (n)

Como no se requiere espacio adicional, no se necesitará espacio adicional .
Por lo tanto, complejidad espacial: O (1)

Gracias por dedicar su tiempo a este artículo. Espero que lo encuentre útil y le brinde una idea clara.

Si aún tiene alguna consulta, no dude en responder. Si lo encuentra útil, compártalo con sus colegas. ¡Tus aplausos me motivan a escribir más blogs de este tipo! 🙂