Перейти Программирование: Комбинации Генерирующие

Question

Это домашнее задание

Я работаю над проектом, и очень маленький (очень маленький, как только я получаю эту работу ... это в основном предварительно REQ для отдыха проекта) часть его состоит в том, чтобы сгенерировать некоторые комбинации с помощью процедуры 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 возвращает 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

Answer 2

Это сложная проблема, если вы совершенно не знакомы с 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 
}