Я написал следующую функцию, чтобы получить все возможные комбинации m из n, отсортированные и без повторения. Я новичок в Go, и мне интересно, какие улучшения я могу сделать с точки зрения производительности и передовых методов.
Ввод: m и массив строк
Вывод: массив всех возможных комбинаций, объединенных в строки
package main
import (
"fmt"
"sort"
"strings"
)
func main() {
var m int64 = 3
items := []string{"b", "a", "d", "e", "f", "c", "k", "h"}
result := FindPossibleCombination(m, items)
fmt.Println( result )
fmt.Println( len(result) )
}
func FindPossibleCombination(m int64, items []string) []string {
sort.Strings(items)
return rec(m, items, 0)
}
func rec(m int64, items []string, start int) []string {
var res []string
n := len(items)
// edge cases
if
int64(n) < m ||
(m == 0 || n == 0) ||
start < 0 ||
m < 0 {
return res
}
// Base case, recursion stops here
if int64(n) == m {
comb := strings.Join(items,"")
return []string{comb}
}
for i := start; i < n; i++ {
// copy items so I don't tamper with the original array
tempArr := make([]string, len(items), cap(items))
copy(tempArr, items)
if i == 0 {
// i = 0: remove last item
tempArr = tempArr[:n-1]
} else {
// i > 0: remove item at len(items) - i
// when i increases move left to remove another item
// until we arrive to m items and recursion stops
copy(tempArr[n-1-i:], tempArr[n-i:])
tempArr[n-1] = ""
tempArr = tempArr[:len(tempArr)-1]
}
// call function again with new array and new start.
// By specifying new start i, we freeze all items to the right of the
// removed item to make sure no combination is repeated.
res = append(res, rec(m, tempArr, i)...)
}
return res
}
Попробуйте на детской площадке:
https://play.golang.org/p/hJN8gatqzud