Permutaciones. Algoritmo lexicográfico.

El algoritmo lexicográfico es un algoritmo de generación de permutaciones que genera todas las permutaciones de un conjunto de elementos en orden lexicográfico. Es similar al algoritmo de Heap, pero en lugar de usar una estructura de datos específica, utiliza una técnica de backtracking para generar las permutaciones. Tiene una complejidad temporal de O(n! * n).


Código Java (LexicographicPermutation.java):

import java.util.Arrays;

public class LexicographicPermutation {
    private static int[] elements = {1, 2, 3, 4, 5, 6, 7, 8};
    private static boolean[] used = new boolean[elements.length];

    public static void main(String[] args) {
        lexicographicPermutation(new int[elements.length], 0);
    }

    private static void lexicographicPermutation(int[] permutation, int index) {
        if (index == elements.length) {
            System.out.println(Arrays.toString(permutation));
            return;
        }

        for (int i = 0; i < elements.length; i++) {
            if (!used[i]) {
                used[i] = true;
                permutation[index] = elements[i];
                lexicographicPermutation(permutation, index + 1);
                used[i] = false;
            }
        }
    }
}


Resultado:

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