combinatorics/combination.go at master · hiroakis/combinatorics · GitHub

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
61
62
package combinatorics

import (
	"sort"
)

func Combination(list []string, n, r int) [][]string {
	var combis [][]string

	var f func(list, data []string, start, end, index, r int)
	f = func(list, data []string, start, end, index, r int) {
		if index == r {
			s := make([]string, len(data))
			copy(s, data)
			combis = append(combis, s)
			return
		}
		for i := start; i <= end && end-i+1 >= r-index; i++ {
			data[index] = list[i]
			f(list, data, i+1, end, index+1, r)
		}
	}

	data := make([]string, r)
	f(list, data, 0, n-1, 0, r)
	return combis
}

func CombinationWithRepetition(list []string, n, r int) [][]string {
	var combis [][]string

	var f func(list, data []string, start, end, index, r int)
	f = func(list, data []string, start, end, index, r int) {
		if index == r {
			s := make([]string, len(data))
			copy(s, data)
			combis = append(combis, s)
			return
		}
		for i := start; i <= end && end-i+r >= r-index; i++ {
			data[index] = list[i]
			f(list, data, i, end, index+1, r)
		}
	}

	data := make([]string, r)
	f(list, data, 0, n-1, 0, r)
	return combis
}

func Unique(in []string) []string {
	m := map[string]struct{}{}
	for _, v := range in {
		m[v] = struct{}{}
	}
	var l []string
	for k := range m {
		l = append(l, k)
	}
	sort.Strings(l)
	return l
}