As part of a learning-Go exercise, I'm writing a simplistic brute-force password cracker.
To generate all possible 2-character passwords that use the characters A-E in Python, I would use itertools.product():
from itertools import product
for permutation in product('ABCDE', repeat=2):
print permutation
However, I'm struggling to do this in Go.
Other questions seem to be about permutations, which isn't quite what I want. And while the Python docs include a sample implementation of the function, I don't know how to translate yield
into Go.
I suppose I should mention two restrictions:
What you want is basically the n-ary cartesian product of a set with itself. So for all 3-character passwords you want Prod(set,set,set). This can be constructed iteratively. First construct the n-1 product, then for each product and each element of the initial set, add the element. So for instance all 2 character passwords -> 3 character passwords where the only valid characters are 'a' or '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 version: http://play.golang.org/p/6LhApeJ1bv
It should be noted that there's a lot of room for improvement on this solution. If you want to construct all passwords of length, say, 6-18, calling this method independently for each one will recalculate previously computed sets. I'll leave writing the better version up to you. Given what I've shown you, it shouldn't be too difficult to modify the code to take an arbitrary (n-m)ary product and compute the n-ary product from it. (Hint: think about how you'd do this recursively)
For example, satisfying your restrictions,
package main
import "fmt"
func nextPassword(n int, c string) func() string {
r := []rune(c)
p := make([]rune, n)
x := make([]int, len(p))
return func() string {
p := p[:len(x)]
for i, xi := range x {
p[i] = r[xi]
}
for i := len(x) - 1; i >= 0; i-- {
x[i]++
if x[i] < len(r) {
break
}
x[i] = 0
if i <= 0 {
x = x[0:0]
break
}
}
return string(p)
}
}
func main() {
np := nextPassword(2, "ABCDE")
for {
pwd := np()
if len(pwd) == 0 {
break
}
fmt.Println(pwd)
}
}
Output:
AA
AB
AC
AD
AE
BA
BB
BC
BD
BE
CA
CB
CC
CD
CE
DA
DB
DC
DD
DE
EA
EB
EC
ED
EE
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With