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 Raw Permalink Blame History

 `/*` `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` ` arr = 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` ```} ``` ``` ```