Implementando next_permutation() en Java con ejemplos

Dada una array o string, la tarea es encontrar la siguiente permutación lexicográficamente mayor en Java.
Ejemplos: 
 

Input: string = "gfg"
Output: ggf

Input: arr[] = {1, 2, 3}
Output: {1, 3, 2}

En C++, hay una función específica que nos ahorra mucho código. Está en el archivo de encabezado #include<algorithm> . La función es next_permutation(a.begin(), a.end()) . Se utiliza para reorganizar los elementos del rango [primero, último] en la siguiente permutación lexicográficamente mayor. Una permutación es cada una de las N! arreglos posibles que pueden tomar los elementos (donde N es el número de elementos en el rango). Se pueden ordenar diferentes permutaciones según cómo se comparan lexicográficamente entre sí.
Aparentemente, Java no proporciona ningún método incorporado de este tipo. Por lo tanto, este artículo analiza cómo implementar la siguiente función de permutación en Java junto con su algoritmo.

Enfoque ingenuo: genere todas las permutaciones posibles del número/string dado, guárdelas en una lista y luego revísela para encontrar la permutación mayor del número dado.

Complejidad del Tiempo= O(n!*n) : n! para generar todas las permutaciones y una n adicional para atravesar y encontrar la permutación mayor.

Space Complexity = O(n!) : para almacenar todas las permutaciones.

Este enfoque es muy ingenuo y complejo de implementar. supongamos que tenemos un tamaño de array de 100, que no es muy grande, pero generará 100. permutaciones que es un número enorme. ¡Además, tendremos que necesitar 100! espacio para almacenarlos todos y luego atravesarlo para encontrar la siguiente permutación mayor.
Algoritmo: 
 

INTUICIÓN DETRÁS DE ESTE ENFOQUE:  Supongamos que tenemos 13542 como nuestra pregunta y tenemos que encontrar su próxima permutación, al observar es claro que cuando recorremos desde el último vemos que los números aumentan hasta 5 y 3 es el primero índice que rompe el orden creciente, por lo tanto, el primer paso:

1. Encuentre el sufijo no creciente más largo y encuentre el pivote (3, es decir, el índice 1 es el pivote).
2. Si el sufijo es la array completa, entonces no hay una permutación de orden superior para los datos (en este caso, haga lo que pide la pregunta, devuelva -1 o la array ordenada).
3. Encuentre el sucesor más a la derecha del pivote: para encontrar el sucesor más a la derecha nuevamente, comience a atravesar desde atrás, en el momento en que encontramos un elemento mayor que el pivote, nos detenemos porque es el elemento requerido (aquí es 4 índice = 3). Esto funciona porque a medida que avanzamos desde atrás, los elementos aumentan linealmente hasta 3 (esta es la primera vez que la array comienza a disminuir), por lo que, en el momento en que encontramos un elemento mayor que 3, es de hecho el elemento mayor o sucesor de 3 y todos los elementos a la izquierda de 4 (hasta 3) son mayores que 3 y todos los elementos a la derecha de 4 son menores que 3.
4. Intercambiar el sucesor y el pivote.
5. Invierta el sufijo: una vez que intercambiamos el sucesor y el pivote, un valor posicional más alto se modifica y se actualiza con un valor mayor, por lo que debe quedar claro que obtendremos la siguiente permutación mayor solo si los elementos después del pivote se organizan en orden creciente. .

A continuación se muestra la implementación del enfoque anterior:
 

// Java program to implement
// the next_permutation method
 
import java.util.Arrays;
 
public class nextPermutation {
 
    // Function to swap the data
    // present in the left and right indices
    public static int[] swap(int data[], int left, int right)
    {
 
        // Swap the data
        int temp = data[left];
        data[left] = data[right];
        data[right] = temp;
 
        // Return the updated array
        return data;
    }
 
    // Function to reverse the sub-array
    // starting from left to the right
    // both inclusive
    public static int[] reverse(int data[], int left, int right)
    {
 
        // Reverse the sub-array
        while (left < right) {
            int temp = data[left];
            data[left++] = data[right];
            data[right--] = temp;
        }
 
        // Return the updated array
        return data;
    }
 
    // Function to find the next permutation
    // of the given integer array
    public static boolean findNextPermutation(int data[])
    {
 
        // If the given dataset is empty
        // or contains only one element
        // next_permutation is not possible
        if (data.length <= 1)
            return false;
 
        int last = data.length - 2;
 
        // find the longest non-increasing suffix
        // and find the pivot
        while (last >= 0) {
            if (data[last] < data[last + 1]) {
                break;
            }
            last--;
        }
 
        // If there is no increasing pair
        // there is no higher order permutation
        if (last < 0)
            return false;
 
        int nextGreater = data.length - 1;
 
        // Find the rightmost successor to the pivot
        for (int i = data.length - 1; i > last; i--) {
            if (data[i] > data[last]) {
                nextGreater = i;
                break;
            }
        }
 
        // Swap the successor and the pivot
        data = swap(data, nextGreater, last);
 
        // Reverse the suffix
        data = reverse(data, last + 1, data.length - 1);
 
        // Return true as the next_permutation is done
        return true;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int data[] = { 1, 2, 3 };
        if (!findNextPermutation(data))
            System.out.println("There is no higher"
                               + " order permutation "
                               + "for the given data.");
        else {
            System.out.println(Arrays.toString(data));
        }
    }
}

[1, 3, 2]

Complejidad temporal: O(n)
Espacio auxiliar: O(1)