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]

Permutaciones. Algoritmo de Heap.

El algoritmo de Heap es un algoritmo de generación de permutaciones que utiliza una estructura de datos conocida como heap. La idea es generar todas las permutaciones de un conjunto de elementos en orden lexicográfico. Tiene una complejidad temporal de O(n!).


Código Java (HeapPermutation.java):

import java.util.Arrays;

public class HeapPermutation {
    private static int[] elements = {1, 2, 3, 4};

    public static void main(String[] args) {
        heapPermutation(elements.length);
    }

    private static void heapPermutation(int size) {
        if (size == 1) {
            System.out.println(Arrays.toString(elements));
            return;
        }

        for (int i = 0; i < size; i++) {
            heapPermutation(size - 1);

            if (size % 2 == 1) {
                int temp = elements[0];
                elements[0] = elements[size - 1];
                elements[size - 1] = temp;
            } else {
                int temp = elements[i];
                elements[i] = elements[size - 1];
                elements[size - 1] = temp;
            }
        }
    }
}


Resultado:

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