53 lines
1.3 KiB
Go
53 lines
1.3 KiB
Go
package combinations
|
|
|
|
// Combinations generates all combinations of r elements from arr.
|
|
func Combinations[V any](arr []V, r int) [][]V {
|
|
n := len(arr)
|
|
|
|
if n == 0 || r == 0 {
|
|
// return an empty combination when no elements or r <= 0
|
|
return [][]V{}
|
|
}
|
|
|
|
result := make([][]V, 0, resultSize(n, r))
|
|
return combinationsIntoSlice(result, arr, n, r)
|
|
}
|
|
|
|
func combinationsIntoSlice[V any](result [][]V, arr []V, n int, r int) [][]V {
|
|
if r == n {
|
|
return [][]V{arr} // Return the original slice if r equals its length
|
|
} else if r == 1 {
|
|
for _, v := range arr {
|
|
result = append(result, []V{v})
|
|
}
|
|
return result // Return individual elements as combinations
|
|
}
|
|
|
|
// Recursive case: generate combinations by including the first element
|
|
head := arr[0]
|
|
tail := arr[1:]
|
|
withHeadCombs := combinationsIntoSlice(result, tail, n-1, r-1)
|
|
for i, comb := range withHeadCombs {
|
|
withHeadCombs[i] = append([]V{head}, comb...)
|
|
}
|
|
|
|
// generate combinations without the first element
|
|
withoutHeadCombs := Combinations(tail, r)
|
|
|
|
return append(withHeadCombs, withoutHeadCombs...)
|
|
}
|
|
|
|
func resultSize(n int, r int) int {
|
|
if n == r {
|
|
return 1
|
|
}
|
|
return factorial(n) / (factorial(r) * factorial(n-r))
|
|
}
|
|
|
|
func factorial(num int) int {
|
|
for i := num - 1; i > 1; i-- {
|
|
num = num * i
|
|
}
|
|
return num
|
|
}
|