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} を生成する必要があります。

私はすべての提案に感謝しますが、「初心者」という用語は囲碁の私の能力を説明し始めていないことを認識してください. 「チャネルを使用してください」などと言っても、まったく役に立ちません。説明は私の友人です...「チャネルを使用する」ことを除いて、教授から得た幸運はあまりありませんでした。

4

2 に答える 2

8

教師は、大きな配列を返す代わりにチャネルを使用する必要があることを既に示唆しています。そのように解決することで、すべての組み合わせを含むこの大きなデータのチャンクを保存する必要がなくなりますが、関数にさまざまな反復を与えて一度に 1 つずつ処理することができます。

が aではなく a をGenerateCombinations返すという点で、先生のヒントが見られます。chan string[]string

func GenerateCombinations(alphabet string, length int) <-chan string

これは、関数が 1) 返すチャネルを作成し、2) 反復をチャネルに供給するゴルーチンを開始する必要があることも意味します。この関数は次のようになります。

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 や順列の生成方法にまったく慣れていない場合、これは難しい問題です。以下は、ソリューションの完全な実装です。本当に行き詰まった場合にのみこれを見ることをお勧めします。そうすることで明らかに学習体験が失われるからです。

外出先のプレイグラウンドで実行して、動作を確認できます。

このアプローチは、インストラクターの例が示唆するように再帰的ではありませんが、仕事は非常にうまく完了します。

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 に答える