Permutation library using Go 1.18's generics
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

68 lines
1.4 KiB

/*
Package permutation implements Heap's algorithm for generating permutations of
lists. It uses Go 1.18's new generics feature to provide a generic interface
*/
package permutation
/*
Permutations uses Heap's Algorithm to generate a list of all possible
permutations of the provided list.
*/
func Permutations[T comparable](arr []T) [][]T {
var heapsAlgo func([]T, int)
var res [][]T
heapsAlgo = func(arr []T, n int) {
if n == 1 {
var tmp []T
for _, i := range arr {
tmp = append(tmp, i)
}
res = append(res, tmp)
} else {
for i := 0; i < n; i++ {
heapsAlgo(arr, n-1)
if n%2 == 1 {
tmp := arr[i]
arr[i] = arr[n-1]
arr[n-1] = tmp
} else {
tmp := arr[0]
arr[0] = arr[n-1]
arr[n-1] = tmp
}
}
}
}
heapsAlgo(arr, len(arr))
return res
}
/*
PermutationsAllSizes returns all permutations of every possible combination in a slice.
This includes single item sets.
*/
func PermutationsAllSizes[T comparable](arr []T) (result [][]T) {
sets := generateSets(arr)
for _, set := range sets {
perms := Permutations(set)
for _, perm := range perms {
result = append(result, perm)
}
}
return result
}
func generateSets[T comparable](arr []T) (result [][]T) {
l := uint(len(arr))
for b := 1; b < (1 << l); b++ {
var s []T
for i := uint(0); i < l; i++ {
if (b>>i)&1 == 1 {
s = append(s, arr[i])
}
}
result = append(result, s)
}
return result
}