Best Practice Alle Kombinationen berechnen

[MaxG.]

Hallo,
ich hab ein Programm geschrieben das alle Kombinationen eines char Arrays berechnen soll.
Ich hab einen Counter mitlaufen lassen um die Anzahl der berechneten Kombinationen auszugeben. Der Counter kommt auf den Wert: 25.774.704 wenn ich aber die Anzahl der möglichen Kombinationen berechne komme ich auf: 71^4= 25.411.681. Wenn man sich den Programmcode ansieht merkt man das dass Array eigentlich 5 und nicht 4 stellen lang ist, allerdings verwende ich ein Leerzeichen als hilfswert. Kann das sein das dass Leerzeichen auch schuld daran ist dass ich 363.023 Kombinationen zu viel hab?
Zudem ist der Code nicht wirklich performant, hat jemand eine bessere Lösung?

public class Combinations{

    static char[] characters = { ' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
            'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',
            'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '1', '2', '3', '4', '5', '6',
            '7', '8', '9', '0', '@', '§', '$', '%', '&', '/', '(', ')' };
    static char[] combination = new char[5];

   
    static int countOfCombinations;
    static long currentTimeMillis;
   
    public static void main(String[] args) {
        // TODO Auto-generated method stub
       
        currentTimeMillis = System.currentTimeMillis();
        calculateCombinations(combination.length);
        System.out.println("______________________________________");
        System.out.println(characters.length);
        System.out.println(countOfCombinations);
        System.out.println("The Programm had run: " + (System.currentTimeMillis() - currentTimeMillis));
    }

    private static void calculateCombinations(int possition) {
        possition--;
        if(possition>0) {
            for(int i = 0; i<characters.length; i++) {
                countOfCombinations++;
                combination[possition] = characters[i];
                System.out.println(new String(combination));
                calculateCombinations(possition);
            }
        }
    }

}

 

[mihe7]

enn man sich den Programmcode ansieht merkt man das dass Array eigentlich 5 und nicht 4 stellen lang ist, allerdings verwende ich ein Leerzeichen als hilfswert. Kann das sein das dass Leerzeichen auch schuld daran ist dass ich 363.023 Kombinationen zu viel hab?

Das Array kannst Du auch mit der Länge 4 definieren. Du musst dann lediglich calculateCombinations() ein wenig umschreiben und natürlich den Aufruf anders gestalten.

Schuld an der Anzahl ist, dass Du nicht nur alle 4-stelligen Kombinationen sondern auch alle 1-, 2-, 3-stellige Kombinationen berücksichtigst. Die Zahl der Kombinationen ist demnach um 71^1 + 71^2 + 71^3 = 363.023 höher.

Zudem ist der Code nicht wirklich performant, hat jemand eine bessere Lösung?

Das liegt nur an der Ausgabe. Gib z. B. nur alle 1.000.000-mal das Ergebnis aus:

            if (countOfCombinations % 1000000 == 0) {
                System.out.println(new String(combination));
            }

 

[MaxG.]

Hi,
danke für deine Antwort.

Schuld an der Anzahl ist, dass Du nicht nur alle 4-stelligen Kombinationen sondern auch alle 1-, 2-, 3-stellige Kombinationen berücksichtigst. Die Zahl der Kombinationen ist demnach um 71^1 + 71^2 + 71^3 = 363.023 höher.

Macht sinn, muss leider zugeben das Mathematik noch nie meine Stärke war.

Das liegt nur an der Ausgabe. Gib z. B. nur alle 1.000.000-mal das Ergebnis aus:

Ich hab den System.out.println() herausgenommen und das Programm hat anstatt ein paar Minuten nur noch ein paar Millisekunden gedauert.

 

[mihe7]

Macht sinn, muss leider zugeben das Mathematik noch nie meine Stärke war.

Das liegt jetzt auch weniger an Mathe sondern an Deinem Algorithmus 🙂

Du fängst mit einem char-Array {0,0,0,0} (ich nehme mal die 4-stellige Variante) an, belegst die letzte Stelle: {0,0,0,' '} und zählst das als eine Kombination. Dann gehst Du eine Stelle nach vorne: {0, 0, ' ', ' '} wieder eine Kombination. Das machst Du noch zweimal und erhältst dann erst die erste "echte" Vierer-Kombi {' ', ' ', ' ', ' '}

D. h. Du zählst nicht nur 4-er- sondern auch 1-er-, 2-er- und 3-er-Kombinationen. Und die Zahl derer berechnet sich natürlich genauso: 71^1 einstellige Kombinationen, 71^2 zweistellige usw.