Heap's algorithm with Go Lang for possibile permutations of N objects.

heaps.go

// Suppose we have a permutation containing N different elements. 
// Heap found a systematic method for choosing at each step a pair of elements to switch, 
// in order to produce every possible permutation of these elements exactly once. 
// Let us describe Heap's method in a recursive way. First we set a counter i  to 0. 
// Now we perform the following steps repeatedly until i  is equal to N. 
// We use the algorithm to generate the (N − 1)! permutations of the first N − 1 elements, 
// adjoining the last element to each of these. This generates all of the permutations that 
// end with the last element. Then if N is odd, we switch the first element and the last one, 
// while if N is even we can switch the i th element and the last one (there is no difference between 
// N even and odd in the first iteration). We add one to the counter i and repeat. In each iteration, 
// the algorithm will produce all of the permutations that end with the element that has just been 
// moved to the "last" position. The following pseudocode outputs all permutations of a data array of length N.
// Reference https://en.wikipedia.org/wiki/Heap%27s_algorithm

package main

import "fmt"

func HeapPermutation(a []int, size int) {
	if size == 1 {
		fmt.Println(a)
	}

	for i := 0; i < size; i++ {
		HeapPermutation(a, size-1)

		if size%2 == 1 {
			a[0], a[size-1] = a[size-1], a[0]
		} else {
			a[i], a[size-1] = a[size-1], a[i]
		}
	}
}

func main() {
  	a := []int{1, 2, 3, 4}
  	HeapPermutation(a, len(a))
}

https://en.wikipedia.org/wiki/Heap%27s_algorithm#Frequent_mis-implementations

// Does this version correct:
// https://en.wikipedia.org/wiki/Heap%27s_algorithm#Frequent_mis-implementations

package main

import "fmt"

func permutations(k int, A []int) {
	if k == 1 {
		fmt.Println(A)
	} else {
		permutations(k-1, A)
		for i := 0; i < k-1; i++ {
			if k%2 == 0 {
				A[i], A[k-1] = A[k-1], A[i]
			} else {
				A[0], A[k-1] = A[k-1], A[0]
			}
			permutations(k-1, A)
		}
	}
}

func main() {
	A := []int{1, 2, 3, 4}
	permutations(len(A), A)
}