permutation.go

package main

import (
	"fmt"
	"math/big"
	"sort"
)

func main() {
	for _, p := range Permutations([]int{1, 2, 3, 4}, 1) {
		fmt.Println(p)
	}
}

func Factorial(n int) *big.Int {
	return big.NewInt(0).MulRange(1, int64(n))
}

// Returns the number of permutations (ordered selections) of r elements from
// an n-element set
func P(n int, r int) *big.Int {
	return big.NewInt(0).Div(Factorial(n), Factorial(n-r))
}

func Permutations(set []int, r int) [][]int {
	ps := make([][]int, int(P(len(set), r).Int64()))

	sorted := append([]int(nil), set...)
	sort.Ints(sorted)

	// The counters and thresholds are in reverse order (i.e., counters[0] is
	// for the last element in a permutation)
	counters, thresholds := make([]int, r), make([]int, r)
	for ix := range counters {
		counters[ix], thresholds[ix] = 0, len(set)-r+ix
	}

	current := append([]int(nil), sorted...)
	for ix := range ps {
		ps[ix] = append([]int(nil), current[:r]...)

		// "Increment" the counters
		for k := range counters {
			if counters[k] >= thresholds[k] {
				counters[k] = 0
			} else {
				counters[k] += 1
				break
			}
		}

		setcopy := append([]int(nil), sorted...)
		for i := 0; i < r; i++ {
			c := counters[r-1-i]
			// fmt.Println(setcopy[c])
			current[i], setcopy = setcopy[c], append(setcopy[:c], setcopy[c+1:]...)
			// current[i] = setcopy[c]
			// setcopy = append(setcopy[:c], setcopy[c+1:]...)
		}
		fmt.Println(counters, current, setcopy)
	}

	return ps
}