Juegos III.1. Generador de Sudokus aleatorios.

En esta versión se añade formato al tablero de juego mediante caracteres ASCII.


Código Java (SudokuGenerator.java):

package sudokugenerator;

import java.util.Random;

public class SudokuGenerator {

    private static final int BOARD_SIZE = 9;
    private static final int SUB_GRID_SIZE = 3;
    private static final int NUM_REMOVES = 20;

    public static void main(String[] args) {
        int[][] board = generateSudoku();
        printBoard(board);
    }

    public static int[][] generateSudoku() {
        int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
        populateBoard(board);
        removeCells(board);
        return board;
    }

    private static void populateBoard(int[][] board) {
        if (!solve(board, 0, 0)) {
            throw new IllegalStateException("No se pudo generar un sudoku válido.");
        }
    }

    private static boolean solve(int[][] board, int row, int col) {
        if (col == BOARD_SIZE) {
            col = 0;
            row++;
            if (row == BOARD_SIZE) {
                return true;
            }
        }

        if (board[row][col] != 0) {
            return solve(board, row, col + 1);
        }

        Random rand = new Random();
        for (int num : rand.ints(1, BOARD_SIZE + 1).distinct().limit(BOARD_SIZE).toArray()) {
            if (isValid(board, row, col, num)) {
                board[row][col] = num;
                if (solve(board, row, col + 1)) {
                    return true;
                }
            }
        }

        board[row][col] = 0;
        return false;
    }

    private static boolean isValid(int[][] board, int row, int col, int num) {
        for (int i = 0; i < BOARD_SIZE; i++) {
            if (board[row][i] == num || board[i][col] == num) {
                return false;
            }
        }

        int r = row - row % SUB_GRID_SIZE;
        int c = col - col % SUB_GRID_SIZE;
        for (int i = r; i < r + SUB_GRID_SIZE; i++) {
            for (int j = c; j < c + SUB_GRID_SIZE; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }

        return true;
    }

    private static void removeCells(int[][] board) {
        Random rand = new Random();
        for (int i = 0; i < NUM_REMOVES; i++) {
            int row = rand.nextInt(BOARD_SIZE);
            int col = rand.nextInt(BOARD_SIZE);
            board[row][col] = 0;
        }
    }

    private static void printBoard(int[][] board) {
        System.out.println("+-------+-------+-------+");
        for (int i = 0; i < BOARD_SIZE; i++) {
            System.out.print("| ");
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] == 0) {
                    System.out.print("▓ ");
                } else {
                    System.out.print(board[i][j] + " ");
                }
                if (j % 3 == 2) {
                    System.out.print("| ");
                }
            }
            System.out.println();
            if (i % 3 == 2) {
                System.out.println("+-------+-------+-------+");
            }
        }
    }
}


Resultado:

run:
+-------+-------+-------+
| ▓ 6 3 | 9 7 8 | 1 2 5 |
| 9 7 8 | 5 ▓ ▓ | 6 3 4 |
| 5 2 1 | 4 6 3 | 8 ▓ 9 |
+-------+-------+-------+
| 3 5 9 | 7 2 ▓ | ▓ 1 ▓ |
| 2 1 ▓ | 8 ▓ 4 | 3 9 ▓ |
| ▓ ▓ 4 | 1 3 9 | ▓ 5 7 |
+-------+-------+-------+
| 8 ▓ 2 | 3 4 7 | 5 6 1 |
| 1 4 6 | 2 9 ▓ | 7 ▓ 3 |
| 7 ▓ 5 | ▓ 8 1 | ▓ 4 2 |
+-------+-------+-------+
BUILD SUCCESSFUL (total time: 0 seconds)

Juegos III. Generador de Sudokus aleatorios.

Este generador crea un tablero de Sudoku completamente resuelto utilizando backtracking y luego elimina un número específico de celdas (en este caso 20) para crear el puzzle. Puedes ajustar el número de celdas eliminadas (NUM_REMOVES) para controlar la dificultad del sudoku generado.


Código Java (SudokuGenerator.java):

package sudokugenerator;

import java.util.Random;

public class SudokuGenerator {

    private static final int BOARD_SIZE = 9;
    private static final int SUB_GRID_SIZE = 3;
    private static final int NUM_REMOVES = 20;

    public static void main(String[] args) {
        int[][] board = generateSudoku();
        printBoard(board);
    }

    public static int[][] generateSudoku() {
        int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
        populateBoard(board);
        removeCells(board);
        return board;
    }

    private static void populateBoard(int[][] board) {
        if (!solve(board, 0, 0)) {
            throw new IllegalStateException("No se pudo generar un sudoku válido.");
        }
    }

    private static boolean solve(int[][] board, int row, int col) {
        if (col == BOARD_SIZE) {
            col = 0;
            row++;
            if (row == BOARD_SIZE) {
                return true;
            }
        }

        if (board[row][col] != 0) {
            return solve(board, row, col + 1);
        }

        Random rand = new Random();
        for (int num : rand.ints(1, BOARD_SIZE + 1).distinct().limit(BOARD_SIZE).toArray()) {
            if (isValid(board, row, col, num)) {
                board[row][col] = num;
                if (solve(board, row, col + 1)) {
                    return true;
                }
            }
        }

        board[row][col] = 0;
        return false;
    }

    private static boolean isValid(int[][] board, int row, int col, int num) {
        for (int i = 0; i < BOARD_SIZE; i++) {
            if (board[row][i] == num || board[i][col] == num) {
                return false;
            }
        }

        int r = row - row % SUB_GRID_SIZE;
        int c = col - col % SUB_GRID_SIZE;
        for (int i = r; i < r + SUB_GRID_SIZE; i++) {
            for (int j = c; j < c + SUB_GRID_SIZE; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }

        return true;
    }

    private static void removeCells(int[][] board) {
        Random rand = new Random();
        for (int i = 0; i < NUM_REMOVES; i++) {
            int row = rand.nextInt(BOARD_SIZE);
            int col = rand.nextInt(BOARD_SIZE);
            board[row][col] = 0;
        }
    }

    private static void printBoard(int[][] board) {
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}


Resultado:

2 7 9 4 3 8 1 5 0
3 4 1 0 7 6 2 8 0
6 8 5 2 1 0 7 3 4
9 0 8 3 0 7 0 6 0
4 1 3 9 6 0 8 7 2
5 0 0 1 0 2 4 9 3
7 9 2 6 0 1 3 4 0
0 3 6 7 2 4 9 1 5
1 5 4 0 9 3 0 2 7

Juegos II. Piedra papel tijeras.

Es un juego de manos en el que se selecciona entre piedra, papel o tijeras, con el objetivo de vencer al oponente. La piedra vence a las tijeras, las tijeras vencen al papel y el papel vence a la piedra.


Código Java (PiedraPapelTijeras.java):

import java.util.Random;
import java.util.Random;
import java.util.Scanner;

public class PiedraPapelTijeras {

    public static void main(String[] args) {
        String[] opciones = {"piedra", "papel", "tijeras"};
        Scanner scanner = new Scanner(System.in);
        Random random = new Random();
        int puntajeJugador = 0;
        int puntajeComputadora = 0;
        String respuesta;
        do {
            String computadora = opciones[random.nextInt(opciones.length)];
            System.out.print("Elige Piedra, Papel o Tijeras: ");
            String jugador = scanner.nextLine().toLowerCase();
            System.out.println("Jugador: " + jugador);
            System.out.println("Computadora: " + computadora);
            if (jugador.equals(computadora)) {
                System.out.println("Empate.");
            } else if ((jugador.equals("piedra") && computadora.equals("tijeras"))
                    || (jugador.equals("papel") && computadora.equals("piedra"))
                    || (jugador.equals("tijeras") && computadora.equals("papel"))) {
                System.out.println("Ganaste.");
                puntajeJugador++;
            } else {
                System.out.println("Perdiste.");
                puntajeComputadora++;
            }
            System.out.println("Puntuacion: Jugador " + puntajeJugador + ", Computadora " + puntajeComputadora);
            System.out.print("Quieres jugar de nuevo? (s/n): ");
            respuesta = scanner.nextLine();
        } while (respuesta.equalsIgnoreCase("s"));
    }
}


Resultado:

Elige Piedra, Papel o Tijeras: piedra
Jugador: piedra
Computadora: tijeras
Ganaste.
Puntuacion: Jugador 1, Computadora 0
Quieres jugar de nuevo? (s/n): s
Elige Piedra, Papel o Tijeras: tijeras
Jugador: tijeras
Computadora: papel
Ganaste.
Puntuacion: Jugador 2, Computadora 0
Quieres jugar de nuevo? (s/n): s
Elige Piedra, Papel o Tijeras: papel
Jugador: papel
Computadora: papel
Empate.
Puntuacion: Jugador 2, Computadora 0
Quieres jugar de nuevo? (s/n): s
Elige Piedra, Papel o Tijeras: tijeras
Jugador: tijeras
Computadora: piedra
Perdiste.
Puntuacion: Jugador 2, Computadora 1
Quieres jugar de nuevo? (s/n): n

Juegos I. Guess the number.

En este ejemplo, el programa genera un número aleatorio entre 1 y 100 y le da al usuario un máximo de 10 intentos para adivinar el número correcto. Cada vez que el usuario ingresa un número, el programa verifica si es mayor o menor que el número aleatorio y proporciona una pista.


Código Java (AdivinaNumero.java):

import java.util.Random;
import java.util.Scanner;

public class AdivinaNumero {
    public static void main(String[] args) {
        Random rand = new Random();
        int numeroAleatorio = rand.nextInt(100) + 1; // Genera un numero aleatorio entre 1 y 100
        Scanner sc = new Scanner(System.in);
        int intentos = 0;
        int numeroIngresado = 0;
        while (intentos < 10) { // El usuario tiene un maximo de 10 intentos
            System.out.print("Adivina el numero (entre 1 y 100): ");
            numeroIngresado = sc.nextInt();
            intentos++;
            if (numeroIngresado == numeroAleatorio) { // Si el usuario adivina el numero, sale del loop
                System.out.println("Felicidades! Adivinaste el numero en " + intentos + " intentos.");
                break;
            } else if (numeroIngresado < numeroAleatorio) {
                System.out.println("El numero es mayor.");
            } else {
                System.out.println("El numero es menor.");
            }
        }
        if (intentos == 10) { // Si el usuario agota sus 10 intentos, muestra el numero aleatorio
            System.out.println("Lo siento, agotaste tus intentos. El numero era " + numeroAleatorio + ".");
        }
    }
}


Resultado:

Adivina el numero (entre 1 y 100): 50
El numero es menor.
Adivina el numero (entre 1 y 100): 25
El numero es mayor.
Adivina el numero (entre 1 y 100): 42
El numero es menor.
Adivina el numero (entre 1 y 100): 35
Felicidades! Adivinaste el numero en 4 intentos.

El autómata de clase 4. Patrón 110.

El autómata celular unidimensional basado en la regla 110 de Stephen Wolfram, es un sistema de evolución discreto que sigue reglas simples para generar patrones complejos a partir de una serie inicial de células.

El ejemplo de autómata de clase 4 aquí descrito, produce patrones complejos y no periódicos que pueden ser difíciles de predecir. Estos patrones pueden tener aplicaciones en la generación de números pseudoaleatorios, criptografía y en simulación de sistemas complejos.


Código Java (Regla110.java):

public class Regla110 {
    public static void main(String[] args) {
        int[] cells = new int[64];
        cells[cells.length / 2] = 1;
        int[] newCells = new int[cells.length];

        for (int t = 0; t < 32; t++) {
            printCells(cells);

            for (int i = 1; i < cells.length - 1; i++) {
                int left = cells[i - 1];
                int center = cells[i];
                int right = cells[i + 1];
                newCells[i] = applyRule110(left, center, right);
            }

            System.arraycopy(newCells, 0, cells, 0, cells.length);
        }
    }

    private static void printCells(int[] cells) {
        for (int cell : cells) {
            System.out.print(cell == 0 ? "." : "┼");
        }
        System.out.println();
    }

    private static int applyRule110(int left, int center, int right) {
        int rule = (left << 2) | (center << 1) | right;
        int rule110 = 0b01110110;
        return (rule110 >> rule) & 1;
    }
}


Resultado:

run:
................................┼...............................
...............................┼┼┼..............................
..............................┼..┼┼.............................
.............................┼┼┼┼.┼┼............................
............................┼...┼┼.┼┼...........................
...........................┼┼┼.┼.┼┼.┼┼..........................
..........................┼..┼┼┼┼.┼┼.┼┼.........................
.........................┼┼┼┼...┼┼.┼┼.┼┼........................
........................┼...┼┼.┼.┼┼.┼┼.┼┼.......................
.......................┼┼┼.┼.┼┼┼┼.┼┼.┼┼.┼┼......................
......................┼..┼┼┼┼...┼┼.┼┼.┼┼.┼┼.....................
.....................┼┼┼┼...┼┼.┼.┼┼.┼┼.┼┼.┼┼....................
....................┼...┼┼.┼.┼┼┼┼.┼┼.┼┼.┼┼.┼┼...................
...................┼┼┼.┼.┼┼┼┼...┼┼.┼┼.┼┼.┼┼.┼┼..................
..................┼..┼┼┼┼...┼┼.┼.┼┼.┼┼.┼┼.┼┼.┼┼.................
.................┼┼┼┼...┼┼.┼.┼┼┼┼.┼┼.┼┼.┼┼.┼┼.┼┼................
................┼...┼┼.┼.┼┼┼┼...┼┼.┼┼.┼┼.┼┼.┼┼.┼┼...............
...............┼┼┼.┼.┼┼┼┼...┼┼.┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼..............
..............┼..┼┼┼┼...┼┼.┼.┼┼┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.............
.............┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼............
............┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼...........
...........┼┼┼.┼.┼┼┼┼...┼┼.┼.┼┼┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼..........
..........┼..┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.........
.........┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼........
........┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.......
.......┼┼┼.┼.┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼......
......┼..┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.....
.....┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼....
....┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼...
...┼┼┼.┼.┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼..
..┼..┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.
.┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼.┼┼┼┼...┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼┼.┼.
BUILD SUCCESSFUL (total time: 0 seconds)

Espirales. Graficar Espiral de Fermat.

La espiral de Fermat es una curva logarítmica que se describe mediante una ecuación polar. Esta espiral se caracteriza por tener radios que se expanden logarítmicamente con respecto al ángulo polar. La ecuación de la espiral de Fermat es:

r = a * t^(1/n)

r: Distancia del origen a un punto en la espiral.
a: Constante positiva. Controla la tasa de expansión de los radios en la espiral.
t: Ángulo polar.
n: Exponente de la constante. Determina el grado de curvatura de la espiral y cómo se relaciona con el ángulo polar.


Código Java (FermatSpiral.java):

package fermatspiral;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.geom.Line2D;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class FermatSpiral extends JPanel {

    private static final long serialVersionUID = 1L;
    private static final int MAX_ITER = 512;
    private static final double SCALE = 80;
    private static final double A = 1;
    private static final int N = 3;

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;
        g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        g2d.translate(getWidth() / 2, getHeight() / 2);
        float lineWidth = 0.1f;
        double theta = 0;
        double r;
        g2d.setColor(Color.BLUE);
        double x1 = 0, y1 = 0, x2, y2;
        for (int i = 0; i < MAX_ITER; i++) {
            r = A * Math.pow(theta, 1.0 / N);
            x2 = SCALE * r * Math.cos(theta);
            y2 = SCALE * r * Math.sin(theta);
            g2d.setStroke(new BasicStroke(lineWidth));
            g2d.draw(new Line2D.Double(x1, y1, x2, y2));
            theta += 0.1;
            lineWidth += 0.01;
            x1 = x2;
            y1 = y2;
        }
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame("Spiral Fermat");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new FermatSpiral());
        frame.setSize(new Dimension(800, 800));
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }
    
}

Resultado:

Espirales. Graficar Espiral de Arquímedes.

La espiral de Arquímedes es una curva matemática que se genera mediante la rotación de una recta alrededor de un punto fijo.


Código Java (ArquimedesSpiral.java):

package arquimedesspiral;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import javax.swing.JComponent;
import javax.swing.JFrame;

public class ArquimedesSpiral extends JComponent {

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;

        int width = getWidth();
        int height = getHeight();

        g2d.translate(width / 2, height / 2);
        g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

        double t = 0.1;
        double a = 5;

        int x1 = 0;
        int y1 = 0;

        g2d.setColor(Color.BLUE);

        for (int i = 0; i <= 500; i++) {
            int x2 = (int) (a * t * Math.cos(t));
            int y2 = (int) (a * t * Math.sin(t));

            g2d.setStroke(new BasicStroke((float) i / 100));
            g2d.drawLine(x1, y1, x2, y2);

            x1 = x2;
            y1 = y2;

            t += 0.1;
        }
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new ArquimedesSpiral());
        frame.setSize(800, 800);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }

}


Resultado:

Espirales. Graficar Espiral Logarítmica.

La espiral logarítmica es una curva matemática que se genera a partir de la relación logarítmica entre su distancia radial y su ángulo polar.


Código java (LogarithmicSpiral.java):

package logarithmicspiral;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import javax.swing.JComponent;
import javax.swing.JFrame;

public class LogarithmicSpiral extends JComponent {

@Override
  protected void paintComponent(Graphics g) {
    super.paintComponent(g);
    Graphics2D g2d = (Graphics2D) g;

    int width = getWidth();
    int height = getHeight();

    g2d.translate(width / 2, height / 2);
    g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

    double theta = 0.5;
    double a = 1;
    double b = 0.12;

    int x1 = 0;
    int y1 = 0;

    g2d.setColor(Color.BLUE);

    for (int i = 0; i <= 500; i++) {
      double r = a * Math.exp(b * theta);
      int x2 = (int) (r * Math.cos(theta));
      int y2 = (int) (r * Math.sin(theta));

      g2d.setStroke(new BasicStroke((float) i / 100));
      g2d.drawLine(x1, y1, x2, y2);

      x1 = x2;
      y1 = y2;

      theta += 0.1;
    }
  }

  public static void main(String[] args) {
    JFrame frame = new JFrame();
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.add(new LogarithmicSpiral());
    frame.setSize(800, 800);
    frame.setLocationRelativeTo(null);
    frame.setVisible(true);
  }

}


Resultado:

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]