aoc-2019/common/itertools.go

package common

// Permutations returns all possible permutations of the given ints.
// Source: https://github.com/dolotech/datastructures-algorithms/blob/master/NUMERICSLICEPERMUTATIONGENERATOR.md
func Permutations(xs []int) (res [][]int) {
	var rc func([]int, int)
	rc = func(a []int, k int) {
		if k == len(a) {
			res = append(res, append([]int{}, a...))
		} else {
			for i := k; i < len(xs); i++ {
				a[k], a[i] = a[i], a[k]
				rc(a, k+1)
				a[k], a[i] = a[i], a[k]
			}
		}
	}
	rc(xs, 0)

	return res
}