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! :)