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);
    }

}