go - 生成所有可能的 n 字符密码

Question

作为学习围棋练习的一部分，我正在编写一个简单的暴力密码破解程序。

要在 Python 中生成使用字符 A-E 的所有可能的 2 字符密码，我会使用 itertools.product() :

from itertools import product
for permutation in product('ABCDE', repeat=2):
  print permutation

但是，我很难在 Go 中做到这一点。

Other questions似乎与排列有关，这不是我想要的。虽然 Python 文档包含该函数的示例实现，但我不知道如何将 yield 翻译成 Go。

我想我应该提到两个限制:

1. 我希望密码的长度可变。也就是说，我可能想做 8 个字符的密码，或者 6 个字符的密码，或者其他的。这意味着我们不能只嵌套 n 个循环。
2. 我不想一次把所有这些都记在内存中。

Answer 1

你想要的基本上是n-ary cartesian product与自身的集合。因此，对于所有 3 个字符的密码，您都需要 Prod(set,set,set)。这可以迭代构建。先构造n-1个产品，然后对每个产品和初始集合的每个元素，添加元素。因此，例如所有 2 个字符的密码 -> 3 个字符的密码，其中唯一有效的字符是“a”或“b”。

"ab"= {​​a,b} -> {(a,a),(a,b),(b,a),(b,b)} -> {(a,a,a),(a,a,b),(a,b,a),(a,b,b),(b,a,a),( b,a,b),(b,b,a),(b,b,b)}

func NAryProduct(input string, n int) []string {
    if n <= 0 {
        return nil
    }

    // Copy input into initial product set -- a set of
    // one character sets
    prod := make([]string, len(input))
    for i, char := range input {
        prod[i] = string(char)
    }

    for i := 1; i < n; i++ {
        // The bigger product should be the size of the input times the size of
        // the n-1 size product
        next := make([]string, 0, len(input)*len(prod))

        // Add each char to each word and add it to the new set
        for _, word := range prod {
            for _, char := range input {
                next = append(next, word + string(char))
            }
        }

        prod = next
    }

    return prod
}

Playground 版本:http://play.golang.org/p/6LhApeJ1bv

请注意，此解决方案还有很大的改进空间。如果您想构建所有长度的密码，例如 6-18，则为每个密码独立调用此方法将重新计算先前计算的集合。我会把更好的版本留给你。鉴于我向您展示的内容，修改代码以采用任意 (n-m) 元乘积并从中计算 n 元乘积应该不会太困难。 (提示:考虑如何递归执行此操作)