31.Próxima serie

Para lograr la función de obtener la siguiente permutación, el algoritmo necesita reorganizar la secuencia dada de números en la siguiente permutación más grande en orden lexicográfico.

Si no hay una siguiente permutación mayor, los números se reordenarán en la permutación más pequeña (orden ascendente).

Debe modificarse en su lugar y solo se permite espacio constante adicional.

A continuación se muestran algunos ejemplos, con la entrada en la columna de la izquierda y la salida correspondiente en la columna de la derecha.

1, 2, 3 → 1, 3, 2

3, 2, 1 → 1, 2, 3

1, 1, 5 → 1 , 5, 1

Análisis del significado del problema

Mire un ejemplo específico, una permutación es 124653, cómo encontrar su siguiente permutación, porque la siguiente permutación debe tener como Prefijo 124653 lo más largo posible, así que abre tu cerebro y mira esta secuencia desde atrás. Si hay una siguiente permutación de los siguientes números, el problema está resuelto.

Paso uno: Encuentra el siguiente arreglo completo del último número.

124653, obviamente el último 1 número 3 no tiene siguiente arreglo completo.

Paso 2: Encuentra la siguiente permutación completa de los dos últimos números.

124653, obviamente no hay una siguiente disposición completa de los dos últimos dígitos 53.

Paso 3: Encuentra la siguiente permutación completa de los últimos tres números.

124653, obviamente no hay una siguiente disposición completa de los últimos tres dígitos 653.

-Interludio: Estoy seguro de que todos han visto aquí que si una secuencia es decreciente, entonces no tiene una siguiente permutación.

Paso 4: Encuentra la siguiente permutación completa de los últimos cuatro números.

124653, encontramos que es obvio que los últimos cuatro números 4653 tienen la siguiente permutación completa. Debido a que no está disminuyendo, por ejemplo, 6453 y 5643 se clasifican después de 4653.

Resumimos las operaciones anteriores y resumimos las dos situaciones de terminación de repetir las operaciones anteriores:

1: Compare dos elementos adyacentes de atrás hacia adelante hasta que el primero sea menor que el segundo. y luego parar.

2. Si no hay ningún elemento anterior, significa que este arreglo es decreciente, por lo que no hay un siguiente arreglo para este arreglo.

124653La terminación de este acuerdo es la primera que se introduce anteriormente. Comparando dos elementos adyacentes de atrás hacia adelante, cuando 4

Podemos saber:

1: El prefijo de 124653 y su siguiente permutación es 12 (porque hay un siguiente en 4653 ordenados de modo que el número anterior 12 permanezca sin cambios).

2: Elementos decrecientes por debajo de 4 (la condición de terminación anterior es que el elemento anterior sea más pequeño que el siguiente elemento, aquí está 4

Ahora, comencemos a pensar en cómo encontrar la siguiente permutación de 4653. Primero, asegúrese de que al menos uno de los números después de 4 sea mayor que 4.

4 debe intercambiarse con uno de los tres números en 653 (6, 5). son 4 para usar 6 aquí. Intercambie uno de 5 con 5. ¿Qué pasa si encontramos tal elemento? Como sabemos que los elementos después de 4 están disminuyendo, miramos hacia adelante desde atrás en 653 y encontramos el primero. que 4, que es el número que hay que intercambiar por 4. Aquí encontramos 5, y la secuencia temporal obtenida después del intercambio es 5643. El 643 obtenido después del intercambio también es el siguiente temporal de 4653. La secuencia es 5643, pero dado que el número anterior se hace más grande (4653-》;5643), este último naturalmente se cambiará a orden ascendente y la transformación de 5643 dará como resultado 5346.

Entonces, la siguiente secuencia de 124653 es 125346

Por ejemplo, mira una permutación

125430

Comenzando desde el final, busca la subsecuencia decreciente, 5430, porque no importa cómo ajustes. 5330, es imposible que sea más pequeño que eso, el número se divide naturalmente en dos partes (1, 2) y (5, 4, 3, 0).

El siguiente paso es encontrar la primera parte de esta secuencia, que es más grande que la parte anterior y tiene 3, lo cual también es fácil de entender porque la siguiente debe comenzar desde (1, 3).

Intercambia 3 y 2 para convertirte en (1, 3, 5, 4, 2, 0), luego invierte la última parte para obtener el más pequeño disponible en la última parte.

En este momento se obtiene la siguiente secuencia 130245’.

Pensamiento

Método violento, busca de atrás hacia adelante hasta encontrar un número que satisfaga el intercambio.