Improving efficiency of ArrayList permutations

Question

As a little project I am making a 'password' cracker that just brute forces through all the permutations of the alphabet and numbers and symbols until the password is guessed.

This, of course, is horribly inefficient and I am looking for ways to make it a bit faster.

My idea is to have the permutations happen in order of their size. So right now, it will start with the first character in the ArrayList and continuously add the next character and the guess gets larger and larger and larger. So for example..

An ArrayList that has the values (A, B, C, D), my current program will create the permutations like this:

(A), (A, B), (A, B, C), (A, B, C, D), (A, B, D), (A, B, D, C)

but a more efficient way (as most passwords are not 60+ characters long), would be to go through the permutations like this

(A), (B), (C), (D), (A, B), (A, C), (A, D), (B, A), (B, C) and so on

This is what my current program looks like:

import java.util.ArrayList;
import java.util.Arrays;

public class BruteForce
{

    public static String password = "rand1";

    public static void main(String[] args) {
        ArrayList<Character> characters = new ArrayList<>(Arrays.asList('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', '0', '1', '2', '3',
                '4', '5', '6', '7', '8', '9', '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', '_', '-', '!', '$'));

        initialPermutations(characters);
    }

    public static void initialPermutations(ArrayList<Character> characters) {
        ArrayList<Character> sub = new ArrayList<>();
        finalPermutations(sub, characters);
    }

    public static void finalPermutations(ArrayList<Character> sub, ArrayList<Character> a) {
        int L = a.size();
        char[] cs = new char[sub.size()];
        for(int i = 0; i < cs.length; i++) {
            cs[i] = sub.get(i);
        }

        String output = new String(cs);

        if(output.equals(password)) {
            System.out.println("The password is " + output);
            System.exit(-1);
        }

        if (L == 0) {
            System.out.println(output);
        }else {

            System.out.println(output);
            for (int i = 0; i < L; i++) {
                ArrayList<Character> ab = new ArrayList<>(sub);
                ab.add(a.get(i));
                ArrayList<Character> bc = new ArrayList<>(a);
                bc.remove(i);
                finalPermutations(ab, bc);
            }
        }
    }
}

Any ideas on how to improve this to the more 'efficient' (not actually more efficient just a bit more useful for shorter passwords) method?

Answer 1

public class BruteForce{

    public static String password = "CBA";

    public static Character[] 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', '0', '1', '2', '3',
            '4', '5', '6', '7', '8', '9', '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', '_', '-', '!', '$'};

    public static Integer count = 0;

    public static void main(String[] args) {
        int deep = characters.length;//password deep,default value is from one to characters.length
        rmark:
        for (int i = 1; i <= deep; i++) {
            for (int j = 0; j < characters.length; j++) {
                if(test(i,characters[j].toString())) {
                    break rmark;
                }
            }
        }
    }

    public static boolean test(int deep,String parent) {
        if(deep <= 1) {
            count++;
            System.out.println(parent);
            if(parent.equals(password)) {
                System.out.println("after generating "+count+" strings,we find the password!");
                return true;
            }
            return false;
        }else {
            for (int j = 0; j < characters.length; j++) {
                if(test(deep-1,parent+characters[j].toString())) {
                    return true;
                }
            }
        }
        return false;
    }
}

Answer 2

Just start counting in base x where x is the amount of characters you have. For instance if you'd only care about digits, you would use the regular base 10 system. It's quite trivial to see it this way, that something like 50045 won't ever come before 5.

Doing this is very simple, just take an array that cointains 0 at the beginning, then every time you need a new password, increase the first element by one. If it exceeds the amount of characters you have, just set it to zero and add one to the next one (if it's the last one, push a new element).

You can go a bit simpler than this by just using a simple long (or BigInteger for larger numbers, the long won't be able to contain more than 10 characters for your setup), then to get the characters from this, just recursively take the modulo of the number and the base you are working in, then divide by the base. This would look something like this:

for (long i = 0; i < maxNum; i++) {
    long temp = i;
    String pass = ""; // Use a StringBuilder here when actually attempting this
    // This would eat your memory faster than 6 chrome tabs
    do {
        pass += charset[temp % base];
        temp /= base;
    }  while (temp > 0);
}