编程:生成组合

Question

这是功课

我正在研究一个项目,而且非常小(非常小,一旦我开始工作......它基本上是项目其余部分的预先请求),部分原因是使用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来描述我的能力.说"使用渠道"之类的东西根本无济于事.解释是我的朋友......除了"使用频道"之外,我没有从我的教授那里得到很多运气.

Answer 1

你的老师已经暗示你应该使用一个频道而不是返回一个大阵列.通过这样解决,您不必存储包含所有组合的大块数据,而是通过不同的迭代来提供您的函数并一次处理一个.

我们可以看到你的老师提示GenerateCombinations返回a chan 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