Permutations

perm.go

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

// Naive solution, create a new array and copy elements in right order. This
// takes O(n) space and O(n) time (the requirement to be inplace adds O(n) time
// additionaly for the back-copy)
func Naive(vals, perm []int) {
	res := make([]int, len(vals))
	for i := range vals {
		res[perm[i]] = vals[i]
	}
	copy(vals, res)
}

// Solution using the permutation to sort the array. This takes approximately
// O(log(n)) space (for the sorting algorithm) and O(n•log(n)) time
type PermSorter struct {
	vals []int
	perm []int
}

func (p PermSorter) Len() int {
	return len(p.vals)
}

func (p PermSorter) Less(i, j int) bool {
	return p.perm[i] < p.perm[j]
}

func (p PermSorter) Swap(i, j int) {
	p.vals[i], p.vals[j] = p.vals[j], p.vals[i]
	p.perm[i], p.perm[j] = p.perm[j], p.perm[i]
}

func Sort(vals, perm []int) {
	sort.Sort(PermSorter{vals, perm})
}

// Solution using the permutation to sort the array, preserving perm. This
// takes approximately O(log(n)) space (for the sorting algorithm) and
// O(n•log(n)) time
type NDPermSorter struct {
	vals []int
	perm []int
}

func (p NDPermSorter) Len() int {
	return len(p.vals)
}

func (p NDPermSorter) Less(i, j int) bool {
	return p.perm[p.vals[i]] < p.perm[p.vals[j]]
}

func (p NDPermSorter) Swap(i, j int) {
	p.vals[i], p.vals[j] = p.vals[j], p.vals[i]
}

func NDSort(vals, perm []int) {
	sort.Sort(NDPermSorter{vals, perm})
}

// Resolve Cycles
func Cycles(vals, perm []int) {
	for i := 0; i < len(vals); i++ {
		v, j := vals[i], perm[i]
		for j != i {
			vals[j], v = v, vals[j]
			perm[j], j = j, perm[j]
		}
		vals[i], perm[i] = v, i
	}
}

// Non-Destructive Cycles
func NDCycles(vals, perm []int) {
	for i := 0; i < len(vals); i++ {
		if perm[i] < 0 {
			perm[i] = ^perm[i]
			continue
		}

		v, j := vals[i], perm[i]
		for j != i {
			vals[j], v = v, vals[j]
			perm[j], j = ^perm[j], perm[j]
		}
		vals[i] = v
	}
}

func main() {
	rand.Seed(time.Now().UnixNano())

	n := 20

	permutation := rand.Perm(n)
	fmt.Println(permutation)
	fmt.Println()

	for _, f := range []func([]int, []int){Naive, Sort, NDSort, Cycles, NDCycles} {
		vals := make([]int, n)
		for i := 0; i < n; i++ {
			vals[i] = i
		}

		perm := make([]int, n)
		copy(perm, permutation)
		f(vals, perm)
		fmt.Println(vals)
		fmt.Println(perm)
		fmt.Println()
	}
}

perm_test.go

package main

import (
	"math/rand"
	"testing"
)

var n = 100

func vals(n int, b *testing.B) []int {
	b.StopTimer()
	res := make([]int, n)
	for i := range res {
		res[i] = i
	}
	b.StartTimer()
	return res
}

func BenchmarkNaive(b *testing.B) {
	perm := rand.Perm(n)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		Naive(vals(n, b), perm)
	}
}

func BenchmarkCycle(b *testing.B) {
	perm := rand.Perm(n)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		NDCycles(vals(n, b), perm)
	}
}

func BenchmarkSort(b *testing.B) {
	perm := rand.Perm(n)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		NDSort(vals(n, b), perm)
	}
}