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]