Java Permutationen werden zu lange berechnet

[Duardo]

Hallo, in meinem Programm werden die Permutationen einer Zahlenfolge berechnet und je nach Inhalt der JComboBox gekürzt. Dieser Vorgang dauert jedoch ziemlich lange. Wenn die Zahlenfolge 7-stellig ist, dauert der Vorgang ca. eine Minute. Ist die Zahlenfolge 10-stellig dauert es sogar mehrere Stunden. Ich denke es hat etwas mit den ganzen Abfragen zu tun. Könnt ihr mir Tipps geben, wie ich den Code "schneller" machen kann? Java mehr Ram zuweisen habe ich schon versucht, jedoch merke ich keinen Unterschied. Hier mein Code, es geht um die permute Methode:

import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Vector;

import javax.swing.DefaultComboBoxModel;
import javax.swing.JButton;
import javax.swing.JComboBox;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.ScrollPaneConstants;

public class test extends JFrame implements ActionListener {
   
    private JPanel panel;
    private JButton ok;
    private JTextArea text;
    private JComboBox drop;
    private DefaultComboBoxModel model;
    private Vector zahlen;
    private String str;
    private String a, b;
    private int zahlKombi;
    private JScrollPane scroll;
   
    public test() {
       
        panel = new JPanel();
        drop = new JComboBox();
        ok = new JButton("OK");
        ok.addActionListener(this);
        str = ("1, 2, 3, 4, 5, 6, 7, ");
        text = new JTextArea(str, 16, 16);
        text.setEditable(true);   
        scroll = new JScrollPane(text);
        scroll.setVerticalScrollBarPolicy(ScrollPaneConstants.VERTICAL_SCROLLBAR_AS_NEEDED);
       
        zahlen = new Vector<Integer>();
        int i = 0;
        for (i=3; i<11; i++) {
            zahlen.add(i); }
       
        model = new DefaultComboBoxModel(zahlen);
        drop.setModel(model);
   
        panel.add(scroll);
        panel.add(ok);
        panel.add(drop);
       
        add(panel);   
       
        pack();
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setVisible(true);
    }

    public static void main(String[] args) {
        new test();
    }
   
    public void normaleKombination() {
        text.setText(b + "&" + "\n");
    }
   
    //-----------------------------------------------------------------------------------hier
    public void permute(java.util.List<Integer> intList, int k){
        for(int i = k; i < intList.size(); i++){ 
                java.util.Collections.swap(intList, i, k);
                permute(intList, k+1);
                java.util.Collections.swap(intList, k, i);
        }
        if (k == intList.size() -1){
            text.append(Arrays.toString(intList.toArray()) + ", ");
            b=text.getText();
            b = b.replace( "[", "" );
            b = b.replace( "]", "" );
            if (zahlKombi >= intList.size()) {
                normaleKombination();
            }
            else {        
                for (int i = 0; i < (intList.size() -zahlKombi); i++) {
                    if (intList.get(intList.size() -(i+1)) >9 && intList.get(intList.size() -(i+1)) <99) {
                        b = b.substring(0, b.length() - 4);
                    }
                    else {
                        if (intList.get(intList.size() -(i+1)) == 100) {
                            b = b.substring(0, b.length() - 5);
                        }
                        else {
                            b = b.substring(0, b.length() - 3);
                        }
                    }
                }
                text.setText(b + "&" + "\n");
            }
        }    
    } 
    //-----------------------------------------------------------------------------------
   
    @Override
    public void actionPerformed(ActionEvent arg0) {
        int k = 0;
        int i = 0;
        zahlKombi = (int)drop.getSelectedItem();
        a = text.getText();   
        text.setText("");
   
        String[] zahlenstring = a.split(", ");
        int[] zahlenint = new int[zahlenstring.length];
       
        for(i = 0; i < zahlenstring.length ;i++) {
            zahlenint[i] = Integer.parseInt(zahlenstring[i]);
        }
       
        ArrayList<Integer> intList = new ArrayList<Integer>();
        for (i = 0; i < zahlenint.length; i++) {
            intList.add(zahlenint[i]);
        }

        permute(intList, k);

    }
}

Wenn noch Unklarheiten bestehen dann fragt einfach nochmal nach. Schonmal Danke im voraus.

 

[InfectedBytes]

Mal so nebenbei, Permutationen zu berechnen ist nunmal eine aufwändige Sache.
Die Laufzeit liegt in O(n!) (n fakultät)
d.h. die die permutationen einer 10 Stelligen Zahl zu berechnen dauert 10 mal so lange wie bei einer 9-Stelligen.
Oder am beispiel von deinen 7 und 10 Stelligen. Dauert die 10 Stellige eben 10*9*8=720 mal solange wie bei einer 7 Stelligen Permutation.

 

[DrZoidberg]

Du führst viel zu viele String Operationen aus. Und die dann auch noch unnötigerweise mit dem gesamten String.
Ersetze deine permute Methode mal hiermit.

public void permute(java.util.List<Integer> intList, int k, int max) {
  if(k == max) {
    text.append(Arrays.toString(intList.subList(0, max).toArray()).replaceAll( "\\[|\\]", "") + ", &\n");
  } else {
    for(int i = k; i < intList.size(); i++){
      java.util.Collections.swap(intList, i, k);
      permute(intList, k+1, max);
      java.util.Collections.swap(intList, k, i);
    }
  }

Aufrufen kannst die diese Methode dann mit
permute(intList, 0, zahlKombi);

 

[Duardo]

@DrZoidberg Vielen Dank, das ist jetzt wirklich ein enormer Unterschied. Denmächst werde ich mehr auf unnötige String Operationen achten!