7

这是作业

我正在做一个项目，其中一个非常小（非常小，一旦我开始工作......它基本上是项目其余部分的先决条件）的一部分是使用 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 能力。说“使用频道”之类的话对我一点帮助都没有。解释是我的朋友……除了“使用渠道”之外，我从教授那里得到的运气并不好。

4

2 回答 2

8

您的老师已经暗示您应该使用通道而不是返回大数组。通过这样解决它，您将不必存储包含所有组合的大量数据，而是为您的函数提供不同的迭代并一次处理它们。

我们可以看到您的老师暗示GenerateCombinations返回 achan string而不是 a []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

于 2013-10-08T14:06:47.287 回答
4

如果您完全不熟悉 Go 和/或如何生成排列，这是一个棘手的问题。以下是该解决方案的完整实现。我建议你只在你真的卡住的时候才看这个，因为这样做显然会消除学习经验。

您可以在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
}
于 2013-10-08T14:43:04.573 回答