Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Permutations
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()
}
}
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)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment