1

在下面的代码中，我试图通过所有可能的字母组合来获取运行时变量的字符数。

这段代码的目的是构建一种密码破解程序，它基本上是暴力破解字符串。我想使用循环，因为一旦命中正确的组合，我就能够打破循环，从而节省时间和资源，否则如果我尝试在第一步中构建所有可能组合的数组，则将需要这些时间和资源。

我有一个静态代码，它适用于 5 个字符长的字符串，但实际上我的字符串可以是任意长度。如何使我的代码适用于任何长度的字符串？

let len = textField.text?.characters.count //Length of string
let charRange = "abcdefghijklmnopqrstuvwxyz" //Allowed characterset

for char1 in charRange.characters {
    for char2 in charRange.characters {
        for char3 in charRange.characters {
            for char4 in charRange.characters {
                for char5 in charRange.characters {
                     // Do whatever with all possible combinations
                }
            }
        }
    }
}

我想我必须以for totalChars in 1...len {某种方式利用，但无法弄清楚如何动态创建 for 循环？

4

3 回答 3

1

正如Martin R所建议的，您可以使用递归

这是功能

func visit(alphabet:[Character], combination:[Character], inout combinations:[String], length: Int) {
    guard length > 0 else {
        combinations.append(String(combination))
        return
    }

    alphabet.forEach {
        visit(alphabet, combination: combination + [$0], combinations: &combinations, length: length - 1)
    }
}

辅助函数

func combinations(alphabet: String, length: Int) -> [String] {
    var combinations = [String]()
    visit([Character](alphabet.characters), combination: [Character](), combinations: &combinations, length: length)
    return combinations
}

测试

现在，如果您想要 3 个字符的每个组合，并且您想要"ab"作为字母表，那么

combinations("ab", length: 3) // ["aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"]

重复

请注意，如果您在字母表中插入重复项，您将在结果中获得重复的元素。

时间复杂度

该visit函数被调用的次数与节点进入k-ary具有高度的完美树一样多，h其中：

  • kalphabet:参数中的元素数量
  • h:length参数

这样的树有

在此处输入图像描述

节点。这是函数将被调用的确切次数。

空间复杂度

理论上为执行访问同时分配的最大栈帧数为length。

然而，由于 Swift 编译器确实实现了尾调用优化，因此分配的堆栈帧数仅为 1。

最后，我们必须考虑combinations将与结果的数量一样大：alphabet^length

所以时间复杂度是 和 的length最大值elements into the result。

它是O(length + alphabet^length)

更新

事实证明，您想要一个蛮力密码破解器。

func find(alphabet:[Character], combination:[Character] = [Character](), length: Int, check: (keyword:String) -> Bool) -> String? {
    guard length > 0 else {
        let keyword = String(combination)
        return check(keyword: keyword) ? keyword : nil
    }

    for char in alphabet {
        if let keyword = find(alphabet, combination: combination + [char], length: length - 1, check: check) {
            return keyword
        }
    }

    return nil
}

最后一个参数check是一个闭包，用于验证当前单词是否是正确的密码。你将把你的逻辑放在这里，find一旦找到密码就会停止。

例子

find([Character]("tabcdefghil".characters), length: 3) { (keyword) -> Bool in
    return keyword == "cat" // write your code to verify the password here
}
于 2016-04-21T18:15:44.320 回答
1

想法：使用字母表中的索引数组形成字符串；每次增加索引。

[0, 0, 0] -> [1, 0, 0] -> [2, 0, 0] ->
[0, 1, 0] -> [1, 1, 0] -> [2, 1, 0] ->
[0, 2, 0] -> [1, 2, 0] -> [2, 2, 0] ->
[0, 0, 1] ... [2, 2, 2]

这是一个使用长度为 3 和字母表的示例abcd

let len = 3
let alphabet = "abcd".characters.map({ String($0) })
var allStrings = [String]()
let maxIndex = alphabet.endIndex
var indicies = Array(count: len, repeatedValue: 0)

outerLoop: while (true) {
    // Generate string from indicies
    var string = ""
    for i in indicies {
        let letter = alphabet[i]
        string += letter
    }
    allStrings.append(string)
    print("Adding \(string)")

    // Increment the index
    indicies[0] += 1

    var idx = 0
    // If idx overflows then (idx) = 0 and (idx + 1) += 1 and try next
    while (indicies[idx] == maxIndex) {
        // Reset current
        indicies[idx] = 0
        // Increment next (as long as we haven't hit the end done)
        idx += 1
        if (idx >= alphabet.endIndex - 1) {
            print("Breaking outer loop")
            break outerLoop
        }
        indicies[idx] += 1
    }
}

print("All Strings: \(allStrings)")
于 2016-04-21T18:17:38.140 回答
1

递归的替代方案；字母表的增量（重复）遍历的循环基数表示

递归的另一种方法是循环遍历字母表的数字表示，使用代表不同数量字母的基数。此方法的一个限制是String(_:,radix:)初始化程序最多允许 base36 数字（基数 36），即您最多可以使用一组唯一计数 <=36 的字符执行“密码破解”。

帮助功能

// help function to use to pad incremental alphabeth cycling to e.g. "aa..."
let padToTemplate: (str: String, withTemplate: String) -> String = {
    return $0.characters.count < $1.characters.count
        ? String($1.characters.suffixFrom($0.characters.endIndex)) + $0
        : $0
}

主要的基数暴力密码检查方法

// attempt brute-force attempts to crack isCorrectPassword closure
// for a given alphabet, suspected word length and for a maximum number of 
// attempts, optionally with a set starting point
func bruteForce(isCorrectPassword: (String) -> Bool, forAlphabet alphabet: [Character], forWordLength wordLength: Int, forNumberOfAttempts numAttempts: Int, startingFrom start: Int = 0) -> (Int, String?) {
    
    // remove duplicate characters (but preserve order)
    var exists: [Character:Bool] = [:]
    let uniqueAlphabet = Array(alphabet.filter { return exists.updateValue(true, forKey: $0) == nil })
    
    // limitation: allows at most base36 radix
    guard case let radix = uniqueAlphabet.count
        where radix < 37 else {
        return (-1, nil)
    }
    
    // begin brute-force attempts
    for i in start..<start+numAttempts {
        let baseStr = String(i, radix: radix).characters
            .flatMap { Int(String($0), radix: radix) }
            .map { String(uniqueAlphabet[$0]) }
            .joinWithSeparator("")
        
        // construct attempt of correct length
        let attempt = padToTemplate(str: baseStr,
            withTemplate: String(count: wordLength, repeatedValue: alphabet.first!))
        
        // log
        //print(i, attempt)
        
        // test attempt
        if isCorrectPassword(attempt) { return (i, attempt) }
    }
    return (start+numAttempts, nil) // next to test
}

示例用法

示例用法 #1

// unknown content closure
let someHashBashing : (String) -> Bool = {
    return $0 == "ask"
}

// setup alphabet
let alphabet = [Character]("abcdefghijklmnopqrstuvwxyz".characters)

// any success for 500 attempts?
if case (let i, .Some(let password)) =
    bruteForce(someHashBashing, forAlphabet: alphabet,
               forWordLength: 3, forNumberOfAttempts: 500) {
    print("Password cracked: \(password) (attempt \(i))")
} /* Password cracked: ask (attempt 478) */

示例用法 #2（与另一个一起拾取一个失败的“批次”）

// unknown content closure
let someHashBashing : (String) -> Bool = {
    return $0 == "axk"
}

// setup alphabet
let alphabet = [Character]("abcdefghijklmnopqrstuvwxyz".characters)

// any success for 500 attempts?
let firstAttempt = bruteForce(someHashBashing, forAlphabet: alphabet,
                              forWordLength: 3, forNumberOfAttempts: 500)
if let password = firstAttempt.1 {
    print("Password cracked: \(password) (attempt \(firstAttempt.0))")
}
// if not, try another 500?
else {
    if case (let i, .Some(let password)) =
        bruteForce(someHashBashing, forAlphabet: alphabet,
                   forWordLength: 3, forNumberOfAttempts: 500,
                   startingFrom: firstAttempt.0) {
        print("Password cracked: \(password) (attempt \(i))")
    } /* Password cracked: axk (attempt 608) */
}
于 2016-04-21T20:15:06.110 回答