Generate all permutations in go
I am looking for a way to generate all possible permutations of a list of elements. Something similar to Python itertools.permutations(arr)
permutations ([])
[]
permutations ([1])
[1]
permutations ([1,2])
[1, 2]
[2, 1]
permutations ([1,2,3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
The difference is that I don't care if the permutations are generated on demand (like a generator in python) or both. I don't care if they are lexicographically sorted either. All I need is to somehow get this n!
Permutation.
source to share
There are many algorithms that generate permutations . One of the simplest I've found is the heap algorithm :
It generates each permutation from the previous one by choosing a pair of elements to exchange.
The idea and pseudocode that prints permutations one by one is outlined in the above link. Here is my implementation of an algorithm that returns all permutations
func permutations(arr []int)[][]int{
var helper func([]int, int)
res := [][]int{}
helper = func(arr []int, n int){
if n == 1{
tmp := make([]int, len(arr))
copy(tmp, arr)
res = append(res, tmp)
} else {
for i := 0; i < n; i++{
helper(arr, n - 1)
if n % 2 == 1{
tmp := arr[i]
arr[i] = arr[n - 1]
arr[n - 1] = tmp
} else {
tmp := arr[0]
arr[0] = arr[n - 1]
arr[n - 1] = tmp
}
}
}
}
helper(arr, len(arr))
return res
}
and here is an example of how to use it ( Go to Site ):
arr := []int{1, 2, 3}
fmt.Println(permutations(arr))
[[1 2 3] [2 1 3] [3 2 1] [2 3 1] [3 1 2] [1 3 2]]
One thing to note is that permutations are not sorted lexicographically (as you saw in itertools.permutations
). If for some reason you need it to be sorted, I found that it has to generate them from the factorial number system (this is described in permutation section
and allows you to quickly find the nth lexicographic permutation).
source to share
Here's code that iterates over all permutations without generating them first. The slice p
stores the intermediate state as an offset in the Fisher-Yates Shuffle algorithm. It has the nice property that a zero value for p
describes an identity permutation.
package main
import "fmt"
func nextPerm(p []int) {
for i := len(p) - 1; i >= 0; i-- {
if i == 0 || p[i] < len(p)-i-1 {
p[i]++
return
}
p[i] = 0
}
}
func getPerm(orig, p []int) []int {
result := append([]int{}, orig...)
for i, v := range p {
result[i], result[i+v] = result[i+v], result[i]
}
return result
}
func main() {
orig := []int{11, 22, 33}
for p := make([]int, len(orig)); p[0] < len(p); nextPerm(p) {
fmt.Println(getPerm(orig, p))
}
}
source to share
don't use recursion! If you want to take advantage of go concurrency and scalability try something like QuickPerm
package main
import (
"fmt"
)
func main() {
for perm := range GeneratePermutations([]int{1,2,3,4,5,6,7}){
fmt.Println(perm)
}
}
func GeneratePermutations(data []int) <-chan []int {
c := make(chan []int)
go func(c chan []int) {
defer close(c)
permutate(c, data)
}(c)
return c
}
func permutate(c chan []int, inputs []int){
output := make([]int, len(inputs))
copy(output, inputs)
c <- output
size := len(inputs)
p := make([]int, size + 1)
for i := 0; i < size + 1; i++ {
p[i] = i;
}
for i := 1; i < size;{
p[i]--
j := 0
if i % 2 == 1 {
j = p[i]
}
tmp := inputs[j]
inputs[j] = inputs[i]
inputs[i] = tmp
output := make([]int, len(inputs))
copy(output, inputs)
c <- output
for i = 1; p[i] == 0; i++{
p[i] = i
}
}
}
source to share
In my case, I had a reference to an array, then I made a few changes to your example:
func generateIntPermutations(array []int, n int, result *[][]int) {
if n == 1 {
*result = append(*result, array)
} else {
for i := 0; i < n; i++ {
generateIntPermutations(array, n-1, result)
if n%2 == 0 {
// Golang allow us to do multiple assignments
array[0], array[n-1] = array[n-1], array[0]
} else {
array[i], array[n-1] = array[n-1], array[i]
}
}
}
}
numbers := []int{0, 1, 2}
var result [][]int
generateIntPermutations(numbers, len(numbers), &result)
// result -> [[2 0 1] [2 0 1] [2 0 1] [2 0 1] [2 0 1] [2 0 1]]
source to share