-
-
Notifications
You must be signed in to change notification settings - Fork 19
/
combinations.go
60 lines (51 loc) · 1.79 KB
/
combinations.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Package combinations provides a method to generate all combinations out of a given generic array.
package combinations
import "math/bits"
// All returns all combinations for a given generic array.
// This is essentially a powerset of the given set except that the empty set is disregarded.
func All[T any](set []T) (subsets [][]T) {
length := uint(len(set))
// Go through all possible combinations of objects
// from 1 (only first object in subset) to 2^length (all objects in subset)
for subsetBits := 1; subsetBits < (1 << length); subsetBits++ {
var subset []T
for object := uint(0); object < length; object++ {
// checks if object is contained in subset
// by checking if bit 'object' is set in subsetBits
if (subsetBits>>object)&1 == 1 {
// add object to subset
subset = append(subset, set[object])
}
}
// add subset to subsets
subsets = append(subsets, subset)
}
return subsets
}
// Combinations returns combinations of n elements for a given generic array.
// For n < 1, it equals to All and returns all combinations.
func Combinations[T any](set []T, n int) (subsets [][]T) {
length := uint(len(set))
if n > len(set) {
n = len(set)
}
// Go through all possible combinations of objects
// from 1 (only first object in subset) to 2^length (all objects in subset)
for subsetBits := 1; subsetBits < (1 << length); subsetBits++ {
if n > 0 && bits.OnesCount(uint(subsetBits)) != n {
continue
}
var subset []T
for object := uint(0); object < length; object++ {
// checks if object is contained in subset
// by checking if bit 'object' is set in subsetBits
if (subsetBits>>object)&1 == 1 {
// add object to subset
subset = append(subset, set[object])
}
}
// add subset to subsets
subsets = append(subsets, subset)
}
return subsets
}