-
Notifications
You must be signed in to change notification settings - Fork 436
/
combinations.go
44 lines (42 loc) · 1.31 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
// Unless explicitly stated otherwise all files in this repository are licensed
// under the Apache License Version 2.0.
// This product includes software developed at Datadog (https://www.datadoghq.com/).
// Copyright 2016 Datadog, Inc.
package lists
// Combinations returns all possible unique selections of size `pick` of a list
// of strings for which order does not matter
//
// an example:
//
// Combinations([cat, dog, bird], 2):
// [cat] -> Combinations([dog, bird], 1)
// [cat, dog]
// [cat, bird]
// [dog] -> Combinations([bird], 1)
// [dog, bird]
// [bird] -> Combinations([], 0)
// n/a
//
func Combinations(list []string, pick int) (all [][]string) {
switch pick {
case 0:
// nothing to do
case 1:
for i := range list {
all = append(all, list[i:i+1])
}
default:
// we recursively find combinations by taking each item in the list
// and then finding the combinations at (pick-1) for the remaining
// items in the list
// the reason we start at [i+1:], is because the order of the items in
// the list doesn't matter, so this will remove all the duplicates we
// would get otherwise
for i := range list {
for _, next := range Combinations(list[i+1:], pick-1) {
all = append(all, append([]string{list[i]}, next...))
}
}
}
return all
}