这是作业
我正在做一个项目,一个非常小的(非常小,一旦我开始工作......它基本上是项目其余部分的先决条件)部分是使用 Go 例程生成一些组合.
我的代码是这样的:
package bruteforce
// GenerateCombinations is an iterator function. Given an alphabet and a
// length, it will generate every possible combination of the letters in
// alphabet of the specified length.
//
// It is meant to be consumed by using the range clause:
//
// for combination := range GenerateCombinations(alphabet, length) {
// process(combination)
// }
//
func GenerateCombinations(alphabet string, length int) <-chan string {
GenerateCombinations(alphabet, length):
if length == 0:
yield ""
else:
for i := range alphabet{
for j := range GenerateCombinations(alphabet, length-1){
i + j
}
}
return nil
}
我真的一点都不明白。正如你所看到的,那里有一些讲师提供的伪代码,但是它的实现却在炒我的脑子。
示例 I/O 是这样的:
如果字母表为{0, 1},密码长度为2,则需要生成{0, 1, 00, 01, 10, 11}。
我感谢所有建议,但请认识到“初学者”一词并不能开始描述我的 go 能力。说“使用频道”之类的话对我一点帮助都没有。解释是我的朋友……除了“使用渠道”之外,我从教授那里得到的运气并不多。
你的老师已经暗示你应该使用通道而不是返回一个大数组。通过这样解决它,您将不必存储包含所有组合的这一大块数据,而是为您的函数提供不同的迭代并一次处理它们。
我们可以看到您的老师暗示
GenerateCombinations
返回 chan string
而不是 []string
:
func GenerateCombinations(alphabet string, length int) <-chan string
这也意味着该函数必须 1) 创建一个返回通道,以及 2) 启动一个 goroutine 将迭代提供给通道。这个函数看起来像这样:
func GenerateCombinations(alphabet string, length int) <-chan string {
c := make(chan string)
// Starting a separate goroutine that will create all the combinations,
// feeding them to the channel c
go func(c chan string) {
defer close(c) // Once the iteration function is finished, we close the channel
// This is where the iteration will take place
// Your teacher's pseudo code uses recursion
// which mean you might want to create a separate function
// that can call itself.
}(c)
return c // Return the channel to the calling function
}
虽然我会将实际迭代留给您,但每个循环都应该导致您将组合字符串放入通道中。因为它不是缓冲通道,所以迭代函数将等待主函数读取值,然后再继续处理下一次迭代。
包含主要功能的游乐场版本:http://play.golang.org/p/CBkSjpmQ0t
使用递归的完整工作解决方案:http://play.golang.org/p/0bWDCibSUJ
如果你完全不熟悉围棋和/或如何生成排列,这是一个棘手的问题。以下是该解决方案的完整实施。我建议你只有在真正卡住的时候才看这个,因为这样做显然会消除学习经验。
您可以在 go playground 上运行它以查看它的工作情况。
这种方法不像您的讲师示例所建议的那样是递归的,但它可以很好地完成工作。
package main
import "fmt"
import "sync"
func main() {
// Make sure the alphabet is sorted.
const alphabet = "abcde"
for str := range generate(alphabet) {
fmt.Println(str)
}
}
func generate(alphabet string) <-chan string {
c := make(chan string, len(alphabet))
go func() {
defer close(c)
if len(alphabet) == 0 {
return
}
// Use a sync.WaitGroup to spawn permutation
// goroutines and allow us to wait for them all
// to finish.
var wg sync.WaitGroup
wg.Add(len(alphabet))
for i := 1; i <= len(alphabet); i++ {
go func(i int) {
// Perform permutation on a subset of
// the alphabet.
Word(alphabet[:i]).Permute(c)
// Signal Waitgroup that we are done.
wg.Done()
}(i)
}
// Wait for all routines to finish.
wg.Wait()
}()
return c
}
type Word []rune
// Permute generates all possible combinations of
// the current word. This assumes the runes are sorted.
func (w Word) Permute(out chan<- string) {
if len(w) <= 1 {
out <- string(w)
return
}
// Write first result manually.
out <- string(w)
// Find and print all remaining permutations.
for w.next() {
out <- string(w)
}
}
// next performs a single permutation by shuffling characters around.
// Returns false if there are no more new permutations.
func (w Word) next() bool {
var left, right int
left = len(w) - 2
for w[left] >= w[left+1] && left >= 1 {
left--
}
if left == 0 && w[left] >= w[left+1] {
return false
}
right = len(w) - 1
for w[left] >= w[right] {
right--
}
w[left], w[right] = w[right], w[left]
left++
right = len(w) - 1
for left < right {
w[left], w[right] = w[right], w[left]
left++
right--
}
return true
}
对于这些任务,您可以尝试 Iterium 包:https://github.com/mowshon/iterium#user-content-combinatorics
product := iterium.Product([]string{"A", "B", "C", "D"}, 2)
toSlice, _ := product.Slice()
fmt.Println("Total:", product.Count())
fmt.Println(toSlice)