Generating permutations in Go
May 15, 2018

A few years ago, while aboard a ferry crossing the Cook Strait, my wife and I were working on some math puzzles and I found myself needing to generate all permutations of a sequence.

Generating permutations is a common task in Project Euler-style puzzles or interview questions; it’s a finger exercise for writing a recursive function. This time, though, I decided to write a package for generating permutations in a more general-purpose way. A little Googling led me to Heap’s algorithm which gives an iterative approach for generating permutations one swap at a time.

I took inspiration from two standard library APIs: sort and bufio.Scanner. The result is github.com/cespare/permute.

The permute package is centered around `permute.Interface`:

``````type Interface interface {
Len() int
Swap(i, j int)
}
``````

`permute.Interface` is a subset of `sort.Interface`: it doesn’t have the `Less` comparison method.

Once you’ve got a type that satisfies this two-method interface, you can generate permutations in place:

``````package main

import (
"fmt"

"github.com/cespare/permute"
)

type Bytes []byte

func (b Bytes) Len() int      { return len(b) }
func (b Bytes) Swap(i, j int) { b[i], b[j] = b[j], b[i] }

func main() {
b := Bytes{'A', 'B', 'C'}
p := permute.New(b)
for p.Permute() {
fmt.Println(string(b))
}
}
``````

Here’s the output:

``````ABC
BAC
CAB
ACB
BCA
CBA
``````

Like the sort package, permute provides a few convenience functions for commonly-permuted types:

``````func Ints(s []int) *Permuter
func Strings(s []string) *Permuter
``````

And that’s it! (You can also consult the documentation.) I’ve only ever used permute once or twice, but it’s a cute little package. Try permuting something with it today! :)