# 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's 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]

With the difference that I do not care whether permutations would be generated on demand (like a generator in python) or all together. I also do not care whether they will be lexicographically sorted. All I need is to somehow get these n! permutations.

## Answers

There are a lot of the algorithms that generate permutations. One of the easiest I found is Heap's algorithm:

It generates each permutation from the previous one by choosing a pair of elements to interchange.

The idea and a pseudocode that prints the permutations one after another is outlined in the above link. Here is my implementation of the algorithm which 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 playground):

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 notice that the permutations are not sorted lexicographically (as you have seen in itertools.permutations). If for some reason you need it to be sorted, one way I have found it is to generate them from a factorial number system (it is described in permutation section and allows to quickly find n-th lexicographical permutation).

**P.S.** you can also take a look at others people code here and here

Here's code that iterates over all permutations without generating them all first. The slice p keeps the intermediate state as offsets in a Fisher-Yates shuffle algorithm. This has the nice property that the zero value for p describes the 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)) } }

don't use recursion! If you want to take advantages of go's 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 } } }

In my case I had a reference to an array, then I've did a few changes in 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]]