69 lines
1.4 KiB
Go
69 lines
1.4 KiB
Go
/*
|
|
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
|
|
}
|