1

tengo un programa con un proceso muy pesado que calcula combinaciones de forma recursiva. Primero calcula todas las combinaciones de n elementos, y luego calcula las combinaciones de las combinaciones anteriores. El proceso se muestra en un progressbar.

Y el problema e que cuando pongo muchas combinaciones el programa se cuelga. Y la verdad no se que sucede ya que si pongo una combinacion menos no se cuelga. Es decir si pongo 7 bienes y 4 herederos no se cuelga. Pero si pongo 8 bienes y 4 herederos empieza la barra de progreso poco a poco pero apenas ha empezado ya no avanza mas.

El programa es para repartir herencias y necesita hacer todas las combinaciones de bienes posibles. El programa tiene dos funciones pesadas: findCombinations, que busca las combinaciones de bienes, y findCombinationsCombinations, que busca las combinaciones de las combinaciones primeras. El realmente pesado es el segundo (findCombinationsCombinations). Entonces no se como resolver esto.

import javax.swing.JFrame;
import javax.swing.JPanel;
import java.awt.*;
import java.awt.event.*;
import java.beans.PropertyChangeEvent;
import java.beans.PropertyChangeListener;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.HashSet;
import java.util.Set;
import javax.swing.*;

public class ProgressBarSwingWorker {

    public JProgressBar progressBar = new JProgressBar();
    Integer count = 1;
    public ArrayList<Bien> A = new ArrayList();
    public int k;
    public int nHerederos = 4;
    public int numerodecombinaciones = 0;
    public int numerodecombinacionescombinaciones = 0;
    public List<List<Bien>> combinaciones = new ArrayList();
    public List<List<List<Bien>>> combinacionesCombinaciones = new ArrayList();
    int n = 0;
    long nCombTotales = 0;
    BigDecimal nCombCombTotales = BigDecimal.valueOf(0);
    JFrame frame = new JFrame("Resultados");
    ProgressPane progressPane = new ProgressPane();

    public long factorial(long numero) {
        long factorial = 1;
        while (numero != 0) {
            factorial = factorial * numero;
            numero--;
        }
        return factorial;
    }

    public long nCombinaciones(long numero, long orden) {
        long nCombinaciones = factorial(numero) / (factorial(orden) * (factorial(numero - orden)));
        return nCombinaciones;
    }

    public BigDecimal factorialBD(BigDecimal numero) {
        BigDecimal factorial = BigDecimal.valueOf(1);
        while (numero != BigDecimal.valueOf(0)) {
            factorial = factorial.multiply(numero);
            numero = numero.subtract(BigDecimal.ONE);
        }
        return factorial;
    }

    public BigDecimal nCombinacionesBD(long numero, long orden) {
        BigDecimal nCombinaciones = factorialBD(BigDecimal.valueOf(numero)).divide((factorialBD(BigDecimal.valueOf(orden)).multiply((factorialBD(BigDecimal.valueOf(numero).subtract(BigDecimal.valueOf(orden)))))));
        return nCombinaciones;
    }

    public void findCombinations(ArrayList<Bien> A, int i, int k,
            Set<java.util.List<Bien>> subarrays,
            java.util.List<Bien> out) {

        // entrada inválida
        if (A.size() == 0 || k > A.size()) {
            return;
        }

        // caso base: el tamaño de la combinación es `k`
        if (k == 0) {

            subarrays.add(new ArrayList<>(out));
            numerodecombinaciones++;
            progressBar.setValue(numerodecombinaciones);
            return;
        }

        // comienza desde el siguiente índice hasta el último índice
        for (int j = i; j < A.size(); j++) {
            // agrega el elemento actual `A[j]` a la solución y repite para el siguiente índice
            // `j+1` con un elemento menos `k-1`
            out.add(A.get(j));
            findCombinations(A, j + 1, k - 1, subarrays, out);
            out.remove(out.size() - 1);        // retractarse

        }
    }

    public void findCombinationsCombinations(java.util.List<java.util.List<Bien>> combinaciones, int i, int k,
            Set<java.util.List<java.util.List<Bien>>> subarrays,
            java.util.List<java.util.List<Bien>> out) {
        // entrada inválida
        if (combinaciones.size() == 0 || k > combinaciones.size()) {
            return;
        }

        // caso base: el tamaño de la combinación es `k`
        if (k == 0) {
            subarrays.add(new ArrayList<>(out));
            numerodecombinacionescombinaciones++;
            progressBar.setValue(numerodecombinaciones + numerodecombinacionescombinaciones);
            return;
        }

        // comienza desde el siguiente índice hasta el último índice
        for (int j = i; j < combinaciones.size(); j++) {
            // agrega el elemento actual `A[j]` a la solución y repite para el siguiente índice
            // `j+1` con un elemento menos `k-1`
            out.add(combinaciones.get(j));

            findCombinationsCombinations(combinaciones, j + 1, k - 1, subarrays, out);
            out.remove(out.size() - 1);        // retractarse
        }
    }

    public Set<List<Bien>> findCombinations(ArrayList<Bien> A, int k) {
        Set<List<Bien>> subarrays = new HashSet<>();
        findCombinations(A, 0, k, subarrays, new ArrayList<>());
        combinaciones.addAll(subarrays);
        return subarrays;
    }

    public Set<List<List<Bien>>> findCombinationsCombinations(List<List<Bien>> combinaciones, int k) {
        Set<java.util.List<java.util.List<Bien>>> subarrays = new HashSet<>();
        findCombinationsCombinations(combinaciones, 0, k, subarrays, new ArrayList<>());
        combinacionesCombinaciones.addAll(subarrays);
        return subarrays;
    }

    public static void main(String[] args) {
        new ProgressBarSwingWorker();
    }

    public ProgressBarSwingWorker() {

        Bien b1 = new Bien("revolta", 1);
        Bien b2 = new Bien("bouzas", 2);
        Bien b3 = new Bien("nazo", 3);
        Bien b4 = new Bien("gradin", 4);
        Bien b5 = new Bien("faro", 5);
        Bien b6 = new Bien("niño de agre", 6);
        Bien b7 = new Bien("gradin", 7);
        Bien b8 = new Bien("faro", 8);
        Bien b9 = new Bien("niño de agre", 9);
        Bien b10 = new Bien("su outeiro", 10);
        A.add(b1);
        A.add(b2);
        A.add(b3);
        A.add(b4);
        A.add(b5);
        A.add(b6);
        A.add(b7);
        A.add(b8);
        //A.add(b9);
        //A.add(b10);

        k = A.size();

        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                try {
                    UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
                } catch (ClassNotFoundException ex) {
                } catch (InstantiationException ex) {
                } catch (IllegalAccessException ex) {
                } catch (UnsupportedLookAndFeelException ex) {
                }

                ProgressPane progressPane = new ProgressPane();

                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.setLayout(new BorderLayout());
                frame.add(progressPane);

                frame.setSize(500, 500);
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);

            }
        });
    }

    public class ProgressPane extends JPanel {

        private JButton startButton;
        public ProgressPane() {
            JPanel panel = new JPanel();
            this.add(panel, BorderLayout.SOUTH);
            setLayout(new GridBagLayout());
            GridBagConstraints gbc = new GridBagConstraints();
            gbc.gridx = 0;
            gbc.gridy = -3;
            add(progressBar, gbc);
            startButton = new JButton("Start");
            gbc.gridy = 1;
            add(startButton, gbc);
            startButton.addActionListener(new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    startButton.setEnabled(false);
                    doWork();
                }
            });

        }

        public void doWork() {

            Worker worker = new Worker();
            worker.addPropertyChangeListener(new PropertyChangeListener() {
                @Override
                public void propertyChange(PropertyChangeEvent evt) {
                    if ("progress".equals(evt.getPropertyName())) {
                    }
                }
            });
            worker.execute();
        }

        public class Worker extends SwingWorker<Object, Object> {

            @Override
            protected void done() {
                startButton.setEnabled(true);
            }

            @Override
            protected Object doInBackground() throws Exception {

                for (int l = 1; l <= k; l++) {
                    nCombTotales += nCombinaciones(A.size(), l);
                }

                nCombCombTotales = nCombinacionesBD(nCombTotales, nHerederos);
                progressBar.setMaximum(nCombCombTotales.intValue() + (int) nCombTotales);

                for (int i = 1; i <= k; i++) {
                    findCombinations(A, i);
                }

                findCombinationsCombinations(combinaciones, nHerederos);

                return null;

            }

        }
    }
}

y esta es la clase Bien:

public class Bien {
    
    private String nombre;
    private double valor;

    public Bien(String nombre, double valor) {
        this.nombre = nombre;
        this.valor = valor;
    }

    public String getNombre() {
        return nombre;
    }

    public void setNombre(String nombre) {
        this.nombre = nombre;
    }

    public double getValor() {
        return valor;
    }

    public void setValor(double valor) {
        this.valor = valor;
    }
    
}
1
  • La recursividad es muy cara y debes evitarla a toda costa. Antes de usar un algoritmo recursivo opta mejor por uno iterativo, y antes de uno iterativo busca primero si existe una fórmula. Ese es el caso de las combinaciones y permutaciones, puedes usar sus fórmulas en lugar de hacerlo por fuerza bruta recursivamente. Commented el 18 ago. 2022 a las 23:46

1 respuesta 1

0

Hay diversos motivos por los que ordenador se quede "congelado" y no responda (creo que te refieres a esto cuando dices que el programa se cuelga).

  1. Monitoriza los recursos mientras estás ejecutando el programa y asegúrate que el programa no consume toda la RAM (No suele llegar a representarse al 100%, pero no deberías de dejar que superara el 90%).
  2. Parece que el programa se ejecuta en un único núcleo. En caso de que no sea así, intenta dejar 1 núcleo para que el proceso que se encarga de actualizar la interfaz pueda tener tiempo de calculo.
  3. Asegúrate que los bucles acaban. En este caso, como estás ejecutando un algoritmo recursivo, tienes que asegurarte que se llama la línea de código base, que hace que no se generen más llamadas.

Tendrías que publicar el mínimo código posible, para que seamos capaces de ir directamente al problema y comentarlo para que entendamos qué estás intentando hacer (porque muchas veces el código hace otra cosa totalmente distinta). Esto también te ayudará a entender tu propio código. Y bueno.. tienes variables y métodos que en un primer vistazo apostaría a que sobran completamente, aunque no importa, todos empezamos igual.

El nombre de la función "findCombinations" da a entender algo erróneo. Parece que quieras buscar la combinación actual "out" en el set de posibles combinaciones "subarrays". Pero lo que entiendo que quieres hacer es crear todas las posibles combinaciones con los elementos de la lista y guardar la combinación que has creado en el set.. tal vez le daría una vuelta al nombre de la función.

El código de la función "findCombinations" que has publicado parece erróneo porque estás añadiendo múltiples veces el mismo elemento; date cuenta que el bucle está añadiendo la "cola" de la lista múltiples veces por la combinación de iteración y recursividad. Todo ello para que en el caso base estés añadiendo sólo 1 combinación (out) al set de posibles combinaciones (subarrays). Ésto es lo que te consume excesiva CPU y encima te obliga a crear otra función "findCombinationsCombinations", que realmente te podrías ahorrar.

Aquí explican cómo generar todas las posibles combinaciones de una lista de elementos en Java utilizando recursividad.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.