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