Как написать алгоритм грубой силы?

Question

Я в настоящее время ищу алгоритм bruteforce, и я просто не могу найти хороший/простой.
Итак, я попытался написать один сам, но я потерпел неудачу. Я слишком плохо разбираюсь в математике или что-то еще. :/
Мне не нужен алгоритм на определенном языке программирования, если он у вас есть, я, возможно, переношу его на нужный мне язык.
Я в основном ищу что-то простое:
(моя попытка написать функцию BruteForce)

function BruteForce(chars,minLen,maxLen) 
    curCharArray = {} 
    for i=1, maxLen do 
     curCharArray[i] = 0 
    end 
    generatedString = "" 
    for currentLength = minLen, maxLen, 1 do 
     curCharArray[currentLength] = 1 
     Pos=currentLength 
     while Pos>0 do 

      if string.len(generatedString) < 1 then 
       generatedString= string.sub(chars,curCharArray[Pos],curCharArray[Pos]) 
      else 
       generatedString= string.sub(generatedString,1,Pos-1) .. string.sub(chars,curCharArray[Pos],curCharArray[Pos]) 
      end 

       print(generatedString) 

      curCharArray[Pos] = curCharArray[Pos]+1 
      Pos = currentLength 
      while curCharArray[Pos]==string.len(chars)+1 do 
       curCharArray[Pos]=1 
       Pos = Pos-1 
      end 
     end 
    end 
end 

BruteForceAttack("abc",2,3) 

это написано в Lua, вы можете запустить код на сайте здесь: http://www.lua.org/cgi-bin/demo выход:

a 
ab 
ac 

a 
ab 
ac 
a 
aa 
ab 
ac 
b 
ba 
bb 
bc 
c 
ca 
cb 
cc 
cca 
ccb 
ccc 
ca 
caa 
cab 
cac 
cb 
cba 
cbb 
cbc 
cc 
cca 
ccb 
ccc 
a 
aa 
aab 
aac 
aa 
aaa 
aab 
aac 
ab 
aba 
abb 
abc 
ac 
aca 
acb 
acc 
b 
ba 
bab 
bac 
ba 
baa 
bab 
bac 
bb 
bba 
bbb 
bbc 
bc 
bca 
bcb 
bcc 
c 
ca 
cab 
cac 
ca 
caa 
cab 
cac 
cb 
cba 
cbb 
cbc 
cc 
cca 
ccb 
ccc 

Как вы можете увидеть некоторые выходы одинаковы, а минимальная длина не рассматривается. Кроме того, порядок неправильный. Я хотел выход быть:

aa 
ab 
ac 
ba 
bb 
bc 
ca 
cb 
cc 
aaa 
aab 
aac 
aba 
abb 
abc 
aca 
acb 
acc 
baa 
bab 
bac 
bba 
bbb 
bbc 
bca 
bcb 
bcc 
caa 
cab 
cac 
cba 
cbb 
cbc 
cca 
ccb 
ccc 

Answer 1

К сожалению, я не знаю LUA, но я думаю, что идея ясна из этого JavaScript сниппета:

function generate(current, len, chars) 
{ 
    if (current.length == len) 
     console.log(current); 
    if (current.length < len) 
     for (var i in chars) { 
      generate(current + chars[i], len, chars) 
     } 
} 

function brute(chars, min, max) 
{ 
    for (var l = min; l <= max; ++l) 
     generate("", l, chars); 
} 

brute(['a', 'b', 'c'], 2, 3); 

UPDATE: Отрывок без рекурсии:

function generateNoRecursion(len, chars) 
{ 
    // Indices that indicate what char to use on corresponding place. 
    var indices = []; 
    for (var i = 0; i < len; ++i) 
     indices.push(0); 

    // While all indices in set of chars 
    while (indices[0] < chars.length) 
    { 
     // Print current solution 
     var str = ""; 
     for (var i = 0; i < indices.length; ++i) 
      str += chars[indices[i]]; 
     console.log(str); 
     // Go to next solution by incrementing last index and adjusting 
     // if it is out of chars set. 
     indices[len-1]++; 
     for (var i = len-1; i > 0 && indices[i] == chars.length; --i) 
     { 
      indices[i] = 0; 
      indices[i-1]++; 
     } 
    } 
} 

function brute(chars, min, max) 
{ 
    for (var l = min; l <= max; ++l) 
     generateNoRecursion(l, chars); 
} 

Answer 2

Многие языки программирования имеют такую ​​возможность в некоторой стандартной библиотеке. Например, в Python, вы можете сделать:

import itertools 

def print_perms(chars, minlen, maxlen): 
    for n in range(minlen, maxlen+1): 
     for perm in itertools.product(chars, repeat=n): 
      print(''.join(perm)) 

print_perms("abc", 2, 3) 

Answer 3

При решении проблемы, существуют различные подходы, такие как:

• Brute-Force: Попробуйте все возможные комбинации состояния, чтобы добраться до решения, путем перечисления комбинации.

• Divide & Conquer: когда состояние проблемы в какой-то момент затруднено, вы делите ее на две или более одинаковые части, которые решаются раздельно, затем частичные решения затем объединяются.

• Динамическое программирование: когда проблема является вариантом на 2 или более измерениях, вы перестраиваете ту же проблему до размера ввода, при каждой сборке вы решаете проблему линейно, используя оптимальное решение, которое вы получили при размере ниже Это.

• Жадный: в каждом состоянии, если это не решение, перейдите в состояние наилучшего соседа, которое в основном оптимизирует (максимизация \ минимизация) за счет стоимости g(state) функции.

• Эвристика: в каждом состоянии у вас есть функция h(state), которая работает как 8-мя шар, рассказывая вам, как близко состояние соседа к состоянию решения.

• .. и т.д.

Eaxmple: Поиск проблем.

-- Brute Force example, search array 

local array = { "apple", "orange", "pear", "banana" } 

for i = 1, #array do 

    if array[i] == "banana" then 

    -- item found 

    end 

end 

Answer 4

Большое спасибо @Dmitry Poroh за хорошую идею. Я реализовал код на Lua:

symbols = {'A','B','C'} 

lenght = {min = 2, max = 3} 

function print_t(t) 
    for _,v in pairs(t) do 
    io.write(v) 
    end 
    print() 
end 

function generate(current, len, chars) 
    if #current == len then 
    print_t(current) 
    return 
    end 
    if #current < len then 
    for c = 1, #chars do 
    curr = {} 
    for i = 1, #current do 
     curr[i] = current[i] 
    end 
    curr[#curr+1] = chars[c] 
    generate(curr, len, chars) 
    end 
    end 
end 

function brute(chars, min, max) 
    for l = min, max do 
    generate({}, l, chars) 
    end 
end 

brute(symbols, lenght.min, lenght.max) 

Результат:

AA 
AB 
AC 
BA 
BB 
BC 
CA 
CB 
CC 
AAA 
AAB 
AAC 
ABA 
ABB 
ABC 
ACA 
ACB 
ACC 
BAA 
BAB 
BAC 
BBA 
BBB 
BBC 
BCA 
BCB 
BCC 
CAA 
CAB 
CAC 
CBA 
CBB 
CBC 
CCA 
CCB 
CCC 

Я надеюсь, что этот код полезен для кого-то.