CODEWITHSUNDEEP
carraysalgorithmbrute-force
Kenshin R.
Kenshin R.

Reputation: 117

Calculate all combinations of a given character set, for brute force matching?

In practising multithreading, I had wished to simply build an application that could calculate all possible combinations of a character set (i.e. brute force cracking/matching) and distributing work among threads, to really get to measure and see first hand how the threading can affect the algorithm's time on different systems.

The algorithm to calculate this, has been a great challenge to me so far. On a recent thread (What would be an efficient way to add multithreading to this simple algorithm?) I seemed to get down what I needed to do (easily pass specific parts of each character range to distribute work) although the algorithm simply did not work, and I did not understand the complexity enough to fix it in my application.

In a simple, iterative manner, how could I compute every combination of a given character set, with a specific length (i.e. 5 in length?)

in example: 

unsigned char range[] = "abcdefghijklmnopqrstuvwxyz0123456789";
brute_force(range, len); //character set, length of string to compute all combinations of
//...

I would be very thankful to relieve some stress on finding the proper concepts of doing this.

Upvotes: 2

Views: 4714

Answers (2)

hugomg
hugomg

Reputation: 69944

Straightfoward iterative bruteforcing for 5 elements:

for c1 in set {
for c2 in set {
for c3 in set {
for c4 in set {
for c5 in set {
    test(c1,c2,c3,c4,c5);
}}}}}

To divide the work between threads, just bive a sepatare "beggining part" for each thread. So first thread handles all wards startting with 'a', second takes the 'b's and so on. (If you have more than 26 threads, then first one gets 'aa' second 'ab' and so on...

If you want a solution that scales better with the length, then it is better to phrase the problem recursevely (If you want, this could be converted into a version using explicit stacks instead):

unsigned char charset = /**/
unsigned int setsize = sizeof charset;

bool test(combination);   

function bruteforce(output, n){
  /* Goes through all character combinations of length n,
     writing them in output and calling test on them afterwards */
  if(n == 0){
    test(output);
  }else{
    for(int i=0; i<setsize; i++){
      output[n-1] = charset[i];
      bruteforce(output, n-1);
    }
  }
}

unsigned char my_output[final_length];
bruteforce(my_output, final_length);

Upvotes: 0

CMR
CMR

Reputation: 985

One approach:

void brute_force(String range, int len) {
        for (int i = 0; i < range.length(); ++i) {
           final String x  = "" + range.charAt(i);
           Thread t = new Thread(){
               public void run() { brute_force(x, range[].replace(x, ""), len); };
            };
            t.start();
        }
}

Where brute_force(String, String, int) will generate the combinations.

Upvotes: 2

Related Questions