Go编程：生成组合

Question

Go编程：生成组合

9

这是一份作业

我正在进行一个项目，其中一个非常小的部分（一旦我完成此部分，它基本上就是接下来项目的前提条件）是使用 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
}

我真的完全不理解这个。你可以看到，那里有一些由教练提供的伪代码，但它的实现让我的大脑崩溃。

例如输入/输出可能是这样的：

如果字母表是 {0, 1} 并且密码长度为 2，那么它需要生成 {0, 1, 00, 01, 10, 11}。

我感谢所有的建议，但请认识到，“初学者”这个术语根本无法描述我在 Go 方面的能力。说一些像“使用通道”的话并没有帮助我。解释才是我的朋友...除了“使用通道”之外，我从我的教授那里并没有得到很多好的解释。

- iMatthewCM

所有这些都是由讲师提供的代码。这也是我困惑的一部分。 - iMatthewCM

3个回答

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
}

- jimt

这也非常有用，如果可以的话，我计划在我的代码中使用几行，当然会标明引用出处。看完整的代码有助于我理解正在发生的事情，而提供的伪代码并不能真正帮到我。 - iMatthewCM

没问题。对我来说，查看完整的、可运行的示例是学习的最佳方式。 - jimt

不错的排列解决方案 :) 。但是，看着Joodoo的例子，老师想要重复排列，而你的是没有重复的。我认为这是为了生成密码暴力破解应用程序。 - ANisus

0

对于这些任务，您可以尝试使用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)

- Mowshon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ANisus · Accepted Answer

你的老师已经暗示你应该使用通道而不是返回一个大数组。通过这种方式解决，你将不必存储包含所有组合的大块数据，而是将不同的迭代提供给你的函数，并逐个处理它们。

我们可以看到你老师的提示是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
}

虽然我将实际迭代留给您自己完成，但每次循环都应该将一个组合字符串放入频道中。由于它不是缓冲频道，迭代函数将等待主函数读取值后才继续处理下一次迭代。

包含主函数的Playground版本：http://play.golang.org/p/CBkSjpmQ0t

使用递归的完整工作解决方案：http://play.golang.org/p/0bWDCibSUJ