Рассчитать все комбинации заданного набора символов для сопоставления грубой силы?

Практикуя многопоточность, я хотел просто создать приложение, которое могло бы вычислять все возможные комбинации набора символов (т. е. взламывать/сопоставлять методом грубой силы) и распределять работу между потоками, чтобы действительно измерить и воочию увидеть, как многопоточность может повлиять на время работы алгоритма в разных системах.

Алгоритм для расчета этого до сих пор был для меня большой проблемой. В недавнем потоке (What было бы эффективным способом добавить многопоточность в этот простой алгоритм?) Я, казалось, понял, что мне нужно было сделать (легко передать определенные части каждого диапазона символов для распределения работы), хотя алгоритм просто не работал, и Я недостаточно понимал сложность, чтобы исправить это в своем приложении.

Простым итеративным образом, как я мог бы вычислить каждую комбинацию заданного набора символов с определенной длиной (т.е. 5 в длину?)

в примере:

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

Я был бы очень благодарен, если бы я избавился от некоторого стресса при поиске правильных концепций для этого.


c arrays algorithm brute-force
person Kenshin R.    schedule 30.04.2011    source источник
comment
Вы хотите комбинации или перестановки? То есть abcde совпадает с edcba?   -  person Jim Mischel    schedule 30.04.2011
comment
Кстати, цифры, с которыми вы имеете дело, довольно велики. Если порядок имеет значение (т. е. вы выполняете перестановки), то 36 элементов, взятых по 5 за раз, составят около 45,2 миллиона. Взятые по 12 за раз, это почти 600 000 000 000 000 000.   -  person Jim Mischel    schedule 30.04.2011
comment
Джером уже предоставил реализацию в простой итерационной манере; просто установите len = 5 stackoverflow.com/questions/1749657/   -  person jfs    schedule 30.04.2011

Ответы (2)


arrow_upward
2
arrow_downward

Один подход:

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

Где brute_force(String, String, int) будет генерировать комбинации.

person CMR    schedule 30.04.2011

arrow_upward
0
arrow_downward

Прямой итеративный брутфорс для 5 элементов:

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

Чтобы разделить работу между потоками, просто создайте отдельную «начальную часть» для каждого потока. Таким образом, первый поток обрабатывает все подопечные, начинающиеся с «а», второй — «б» и так далее. (Если у вас более 26 потоков, то первый получает "aa", второй "ab" и так далее...

Если вам нужно решение, которое лучше масштабируется по длине, то лучше сформулировать проблему рекурсивно (если вы хотите, это можно преобразовать в версию с использованием вместо этого явных стеков):

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);
person hugomg    schedule 30.04.2011