首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何编写蛮力算法?

如何编写蛮力算法?
EN

Stack Overflow用户
提问于 2014-09-17 20:31:57
回答 4查看 11.7K关注 0票数 2

我目前正在寻找一个蛮力算法,我只是找不到一个好的/简单的。

所以我试着自己写一个,但失败了。我只是数学太差了什么的。:/

我不需要在特定的编程语言中的算法,如果你有一个,我可能可以把它移植到我需要它的语言。

我基本上是在寻找这样简单的东西:

(我试图编写一个蛮力函数)

代码语言:javascript
复制
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输出如下:

代码语言:javascript
复制
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

如您所见,一些输出是相同的,并且没有考虑最小长度。而且,命令是错误的。我希望输出是:

代码语言:javascript
复制
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
EN

回答 4

Stack Overflow用户

回答已采纳

发布于 2014-09-17 21:53:28

不幸的是,我不认识LUA,但是我认为从这个JavaScript片段中可以清楚地看到这个想法:

代码语言: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:没有递归的代码片段:

代码语言:javascript
复制
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);
}
票数 5
EN

Stack Overflow用户

发布于 2014-09-17 21:49:57

许多编程语言在某些标准库中具有这样的功能。例如,在Python中,可以这样做:

代码语言:javascript
复制
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)
票数 2
EN

Stack Overflow用户

发布于 2017-04-27 19:33:07

非常感谢德米特里·波洛的好主意。我在lua上实现了代码:

代码语言:javascript
复制
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)

结果:

代码语言:javascript
复制
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

我希望这段代码对某些人有用。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/25899839

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档