brute forcer algorithm with all possible combinations / permutation in a given char array

Question

Need help for this simple thing that is annoying me. I have seen many similar algorithms but I want to do this in exactly the stated way to reach ALL possible combinations / permutation in a given charset array.

lets take an example of a password cracker brute forcer

e.g char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray(); ?

stated way:

its like this. for the current example.

a,b,c,d......z     then at last index "z".  

it goes like      

aa,ab,ac....az.        then      

ba,bb,bc,bd........bz          then

same for ca, cb, and so on.

aaaa,aaab,aaac......aaaz   then

baaa,baab,baac.......baaz   to      zzzzzzzzzzzzzzzzzzzzzzzzzz

Code I reached so far:

(well not a solution though) is to have as many for loops as the length of charset array. that is insane. this works ok. but i need intelligent one.

public class Bruteforcer {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
          char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();


         int currentIndex = 0;
         String currentString = "";

         for (int i = 0; i < charset.length; i++) {
            char currentChar = charset[i];

             for (int j = 0; j < charset.length; j++) {

                 char c = charset[j];
                 currentString =  "" +currentChar + c;
                 System.out.println(currentString);

             }


         }


    }
}

Answer 1

To solve this without recursion, it helps to keep an array of the indices for your current result. Here is a template class that will produce the result you are looking for:

public abstract class Bruteforce
{
  public void generate( char[] input ) {
    char[] result = new char[input.length];
    int[] index = new int[input.length];

    // initialize the arrays.
    Arrays.fill(result, 0, result.length, input[0]);
    Arrays.fill(index,  0, index.length, 0);

    // loop over the output lengths.
    for( int length = 1; length <= input.length; length++ ) {
      int updateIndex = 0;
      do {
        element(result, 0, length);

        // update values that need to reset.
        for(updateIndex = length-1;
            updateIndex != -1 && ++index[updateIndex] == input.length;
            result[updateIndex] = input[0], index[updateIndex] = 0, updateIndex--);

        // update the character that is not resetting, if valid
        if( updateIndex != -1 ) result[updateIndex] = input[index[updateIndex]];
      }
      while(updateIndex != -1);
    }
  }
  public void generate( String input ) {
    generate(input.toCharArray());
  }
  public abstract void element(char[] result, int offset, int length);
}

You can then extend the template to print each element to STDOUT:

new Bruteforce() {
  public void element(char[] result, int offset, int length) {
    System.out.println(new String(result, offset, length));
  }
}.generate("ABCDEFGHIJKLMNOPQRSTUVWXYZ");

NOTE: This code assumes that the input string does not contain any duplicate characters.

Answer 2

You need to use recursion. The complexity of the algorithm is exponential. I hope I understood the problem.

public class Generator {
    private char[] charset;

    public Generator()
    {
        charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
    }


    public void generate(String str, int pos, int length)
    {
        if (length == 0) {
            System.out.println(str);
        } else {
            for (int i = pos; i < charset.length; i++) {
                generate(str + charset[i], i, length - 1);
            }
        }
    }

    public static void main(String[] args)
    {
        Generator test = new Generator();
        //test.generate("", 1);
        for (int length = 1;  length < 5; length++) // Change 5 with the length of charset
            test.generate("", 0, length);
    }

}

Answer 3

public class Generator {

    private char[] charset;

    private int min; //var added for min char length
    private int max; //var added for max char length

    public Generator() {
        charset = "abcdefghijklmnopqrstuvwxyzAEIOU0123456789!@#$%^&*()-_+=~`[]{}|:;<>,.?/BCDFGHJKLMNPQRSTVWXYZ".toCharArray();
        min = 2; //char min start
        max = 5; //char max end 
    }

    public void generate(String str, int pos, int length) {
        if (length == 0) {
            System.out.println(str);
        } else {

            //This if statement resets the char position back to the very first character in the character set ('a'), which makes this a complete solution to an all combinations bruteforce! 
            if (pos != 0) {
                pos = 0;
            }

            for (int i = pos; i < charset.length; i++) {
                generate(str + charset[i], i, length - 1);
            }
        }
    }

    public static void main(String[] args) {
        Generator bruteforce = new Generator();

        for (int length = bruteforce.min; length < bruteforce.max; length++) // Change bruteforce.min and bruteforce.max for number of characters to bruteforce. 
            bruteforce.generate("", 0, length); //prepend_string, pos, length 
    }
}

I've modified rendon's example above- https://stackoverflow.com/revisions/18685721/1 Note: it allow all combinations, and added min and max vars

Answer 4

You can use recusrion and a couple of loops.

public static void printCombinations(int length) {
    printCombinations(new char[length], 0, 0);
}

private static void printCombinations(char[] chars, int idx, int mask) {
    if (idx == chars.length) {
        System.out.println(chars);
        return;
    }
    for (int i = 0; i < 26; i++) {
        int mask2 = 1 << i;
        if ((mask2 & mask) == 0) {
            chars[idx] = (char) ('A' + i);
            printCombinations(chars, idx + 1, mask | mask2);
        }
    }
}

public static void main(String[] args) throws Exception {
    for (int i = 1; i <= 3; i++)
        printCombinations(i);
}

prints

A
B
...
ZYWX ... DCBA

A combination has no repeating characters so it wouldn't be ZZZZZ...

Answer 5

A more object orientated solution

Usage known length

final String target = "ABC";
final char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
BruteForce.bruteForce(charset, 5, string -> {
    System.out.println(string);
    return string.equals(target);
});

Usage unknown length

final String target = "ABC";
final char[] charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();

// Use your looping method of choice
boolean found = false;
int length = 1;
while (!found) {
    found = BruteForce.bruteForce(charset, length, string -> {
        System.out.println(string);
        return string.equals(target);
    });
    length++;
}

Implementation

public class BruteForce {

    public static boolean bruteForce(@NonNull final char[] input, final int length, @NonNull final Closure closure) {
        final char[] chars = new char[length];
        final IncrementalCharSequence incrementalCharSequence = new IncrementalCharSequence(input, chars);

        // Use your looping method of choice
        do {
            if (closure.compare(new String(chars))) {
                return true;
            }
        } while (incrementalCharSequence.increment());
        return false;
    }
}

public interface Closure {

    boolean compare(@NonNull final String string);
}

public class IncrementalCharSequence {

    @NonNull
    private final char[] input;

    @Nullable
    private final IncrementalCharSequence subIncrementalCharSequence;

    @NonNull
    private final char[] chars;

    private final int index;

    private int currentIndex;

    public IncrementalCharSequence(@NonNull final char[] input, @NonNull final char[] chars) {
        this(input, chars, 0);
    }

    private IncrementalCharSequence(@NonNull final char[] input, @NonNull final char[] chars, final int index) {
        this.input = input;
        this.chars = chars;
        this.index = index;
        if (index + 1 < chars.length) {
            this.subIncrementalCharSequence = new IncrementalCharSequence(input, chars, index + 1);
        } else {
            this.subIncrementalCharSequence = null;
        }
        currentIndex = 0;
        chars[index] = input[currentIndex];
    }

    /**
     * Increment the char sequence
     *
     * @return {@code true} if incremented, {@code false} if rolled over to zero index
     */
    public boolean increment() {
        if (subIncrementalCharSequence != null && subIncrementalCharSequence.increment()) {
            return true;
        } else if (currentIndex < input.length) {
            chars[index] = input[currentIndex];
            currentIndex++;
            return true;
        } else {
            currentIndex = 0;
            chars[index] = input[currentIndex];
            return false;
        }
    }
}

Answer 6

A pseudo-code

initialize globalComb, an empty array of strings (to keep all combination)
initialize prevComb, an array of strings with an empty string (the previous set of combination)
while(the length of first string in prevComb is not of desired length)
    initialize temp,  an empty array of strings (a temporary one)
    for(each string s in prevComb)
        for(each char c in the alphabet)
            insert s + c in temp
            insert s + c in globalComb
        end for
    end for
    lastComb = temp
return globalComb

the size of globalComb must be sum(k=1, k=desired length)26^k. If the desired length is 26, I doubt if an average laptop can hold an array of such strings. Instead of storing in a global array, you can just print the strings out.

Answer 7

I have come up with this piece of code this will run to 8 didgets/letters
eg. if you are using just capital letters A to Z:
A
B
...
...
ZZZZZZZY
ZZZZZZZZ

char[] ch = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
for (int i = 0; i < ch.length; i++) {
    char c1 = ch[i];
    for (int j = 0; j < ch.length; j++) {
        char c2 = ch[j];
        for (int k = 0; k < ch.length; k++) {
            char c3 = ch[k];
            for (int l = 0; l < 10; l++) {
                char c4 = ch[l];
                for (int m = 0; m < 10; m++) {
                    char c5 = ch[m];
                    for (int n = 0; n < 10; n++) {
                        char c6 = ch[n];
                        for (int o = 0; o < 10; o++) {
                            char c7 = ch[o];
                            for (int p = 0; p < 10; p++) {
                                char c8 = ch[p];
                                currentString = "" + c1 + c2 + c3 + c4 + c5 + c6 + c7 + c8;
                                System.out.println(currentString);

                            }
                        }
                    }
                }
            }
        }
    }
}