Search code examples
algorithmbrute-force

How to write a brute-force algorithm?


I'm currently looking for a bruteforce algorithm and I just can't find a good/simple one.
So I tried to write one myself, but I failed. I'm just too bad at math or whatever. :/
I don't need the algorithm in a specific programming language, if you have one, I can probably port it to the language I need it in.
I'm basically looking for something as simple as this:
(my attempt to write a bruteforce function)

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)

It's written in Lua, you can run the code online here: http://www.lua.org/cgi-bin/demo The output is:

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

As you can see some outputs are the same and the minimum length is not being considered. Also, the order is wrong. I wanted the output to be:

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

Solution

  • Unfortunately I don't know LUA but I think idea is clear from this JavaScript snippet:

    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: Snippet without recursion:

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