我正在尝试从Go中的this Stackoverflow question移植算法。我正在尝试使用的算法如下:给定任意长度的字符串 slice 和“深度”，找到原始 slice 中长度为深度的元素的所有组合。例如，如果给定一个包含A，B，C，D，E和F且深度为3的 slice ，则结果应为:

[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]

package main

import (
    "fmt"
)

func main() {
    combos := []string{"A","B","C","D","E","F"}
    combos = GetCombos(combos, 3)

    fmt.Println(combos)
}

func GetCombos(set []string, depth int) []string {
    var results []string
    element := make([]string, depth)
    return GetEnvCombos2(set, depth, 0, element, results)
}

func GetCombos2(set []string, depth int, start int, element, results []string) []string {
    if depth == 0 {
        var guess string
        for _, e := range element {
            guess += e
        }
        results = append(results, guess)
        return results
    }
    for i := start; i <= len(set) - depth; i++ {
        element[len(element) - depth] = set[i]
        results = append(results, GetEnvCombos2(set, depth - 1, i + 1, element, results)...)
    }

    return nil
}

最佳答案

注意:

对任何组合问题的正确答案实际上是永远不要将所有可能的组合放入容器中，然后再进行处理。通常会有大量的组合，并且临时容器往往会用完所有可用内存以存储仅将被引用一次的项目。原始Java程序将处理步骤(在本例中为“打印组合”)埋在生成函数的内部，实际上，它也不是一个好的解决方案，因为它需要为每个不同的动作创建一个全新的生成器函数。

构造组合生成的一种方法是使用给定前一个组合的函数，该函数可查找下一个组合。这种功能通常称为“迭代器”。如果提供了最后一个组合，则该函数返回一个返回值，指示没有更多可用组​​合。通常，所提供的组合是“就地”修改的，因此返回值只是一个布尔值，指示组合是否为最后一个组合。 (通常认为最佳做法是将提供的组合重置为第一个组合，并报告以前是最后一个组合。)该策略不适用于递归算法(例如您要移植的组合)。

许多语言都包含一些允许递归生成可能值的功能。例如，在Go中，您可以将迭代器编写为“go例程”。尽管存在潜在的成本，但这可以产生非常精美的代码。

通过使用某种堆栈数据结构模拟调用堆栈，始终可以将递归函数重新实现为迭代函数。但是，结果难以理解，而且通常较慢(因为本机递归几乎总是比模拟递归快)。而且您可能能够找到一种非递归算法进行迭代(可能会更改迭代顺序)。

我不会在这里做任何这些事情。以下内容仅满足与原始代码相同的原型，并返回(可能是巨大的)结果片段，因为根本的问题仅是递归函数的设计问题。

内部递归生成器的原型是

func GetCombos2(set []string,
                depth int, start int,
                element []string,
                results []string) []string

func GetCombos2(set []string, depth int, start int, element []string, results []string) []string {
    if depth == 0 {
        results = append(results, strings.Join(element, "")) 
    } else {
        for i := start; i <= len(set) - depth; i++ {
            element[len(element) - depth] = set[i]
            results = GetEnvCombos2(set, depth - 1, i + 1, element, results)
        }
    }
    return results
}

func GetCombos2(set []string, depth int, start int, element []string) []string {
    if depth == 0 {
        return []string { strings.Join(element, "") }
    } else {
        var results []string
        for i := start; i <= len(set) - depth; i++ {
            element[len(element) - depth] = set[i]
            results = append(results, GetCombos2(set, depth - 1, i + 1, element)...)
        }
        return results
    }
}

func GetCombos(set []string, depth int) []string {
    return GetCombosHelper(set, depth, 0, "", []string{})
}

func GetCombosHelper(set []string, depth int, start int, prefix string, accum []string) []string {
    if depth == 0 {
        return append(accum, prefix)
    } else {
        for i := start; i <= len(set) - depth; i++ {
            accum = GetCombosHelper(set, depth - 1, i + 1, prefix + set[i], accum)
        }
        return accum
    }
}

func GetCombos(set []string, depth int) []string {
    return GetCombosHelper(set, depth, 0, "")
}

func GetCombosHelper(set []string, depth int, start int, prefix string) []string {
    if depth == 0 {
        return []string{prefix}
    } else {
        accum := []string{}
        for i := start; i <= len(set) - depth; i++ {
            accum = append(accum, GetCombosHelper(set, depth - 1, i + 1, prefix + set[i])...)
        }
        return accum
    }
}

关于algorithm - 从N个元素的 slice 生成K个元素的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54054062/