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.

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))
	}
}

var res [][]int
func permute(nums []int) [][]int {
    res=make([][]int,0)
    n:=len(nums)
    var backTrack func(int)
    backTrack=func(first int){
        if first == n{
            temp:=make([]int, n)
            copy(temp,nums)
            res = append(res, temp)
        }
        for i:=first;i<n;i++{
            nums[first],nums[i] = nums[i],nums[first]
            backTrack(first+1)
            nums[first],nums[i] = nums[i],nums[first]
        }
    }
  
    backTrack(0)
    return res
}

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 {
		dst := make([]int, len(array))
		copy(dst, array[:])
		*result = append(*result, dst)
	} 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 -> [[0 1 2] [1 0 2] [2 1 0] [1 2 0] [2 0 1] [0 2 1]]

Another Working code

package permutations

import "fmt"

func AllPermutation(a []int) {
	var res [][]int
	calPermutation(a, &res, 0)
	fmt.Println(res)
}
func calPermutation(arr []int, res *[][]int, k int) {
	for i := k; i < len(arr); i++ {
		swap(arr, i, k)
		calPermutation(arr, res, k+1)
		swap(arr, k, i)
	}
	if k == len(arr)-1 {
		r := make([]int, len(arr))
		copy(r, arr)
		*res = append(*res, r)
		return
	}
}
func swap(arr []int, i, k int) {
	arr[i], arr[k] = arr[k], arr[i]
}
//result [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 2 1] [3 1 2]]

Here is another variation:

// heap algorithm
func permutations(arr []int, l int, p [][]int) [][]int {
  if l == 1 { p = append(p, append([]int{}, arr...)) }
  for i := 0 ; i < l ; i++ {
    p = permutations(arr, l-1, p)
    if l % 2 == 1 {
      arr[0], arr[l-1] = arr[l-1], arr[0]
    } else {
      arr[i], arr[l-1] = arr[l-1], arr[i]
    }
  }
  return p
}

Permutation code using simple algorithm in golang

package main

import "fmt"

func permute(arr[] int, start int, end int) {
        if start == end {
                fmt.Println(arr)
                return
        }
        for i:=start;i<end;i++ {
                arr[i],arr[start] = arr[start],arr[i]
                permute(arr,start+1,end)
                arr[i],arr[start] = arr[start],arr[i]
        }
}

func main() {
        arr := []int{1,2,3}
        end := len(arr)
        start := 0
        permute(arr,start,end)
}

You can use the Iterium package for this task: https://github.com/mowshon/iterium

Example code for your question:

permutations := iterium.Permutations([]string{"A", "B", "C", "D"}, 2)
toSlice, _ := permutations.Slice()

fmt.Println("Total:", permutations.Count())
fmt.Println(toSlice)

Result:

Total: 12

[
    [A, B] [A, C] [A, D] [B, A] [B, C] [B, D]
    [C, B] [C, A] [C, D] [D, B] [D, C] [D, A]
]