Una forma sencilla y rápida de aprender JAVA, observando y deduciendo cómo se comporta el lenguaje a través de ejemplos prácticos.

Archivo del blog

sábado, 28 de enero de 2023

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]

Con la tecnología de Blogger.