Thursday, September 5, 2013

4.3.1: Example - Permutations

The purpose of the Permute iterator is to accept a range such as A..C and write out all possible permutations:


As always, we start with capturing and storing the state of the iteration, i.e. the permuation.

type permute struct {
    items []rune
    n     int
    atEnd bool

func Permute(items []rune) i.Forward {
    return &permute{items: items, n: 1, atEnd: false}

items[] and n are the state of the current permuation while atEnd indicates whether we've listed all possible permuations.

func (p *permute) Error() error {
    return nil

func (p *permute) Value() interface{} {
    return p.items

func (p *permute) AtEnd() bool {
    return p.atEnd

These three functions are very simple, very little to do here apart from the obvious.

func (per *permute) Next() error {
    var i int
    p := per.n
    for i = 1; i <= len(per.items) && math.Mod(float64(p), float64(i)) == 0; i++ {
        p /= i
    d := int(math.Mod(float64(p), float64(i)))
    j := len(per.items) - i
    if j < 0 {
        per.atEnd = true
        return nil

    copy(per.items[j+1:len(per.items)], reverse(per.items[j+1:len(per.items)]))
    per.items[j], per.items[j+d] = per.items[j+d], per.items[j]
    return nil

Next() is where the generation of the next permutation occurs, and if the three before were to simple, this one is to clever by far. The idea is to go through the permuations from the last element to the first, such as:


The first element is held fixed while we go through all permuations of the other elements. Once we are done, we swap the first and second element and go through the process again. If nothing else, it is a very efficient use of modular mathematics and vectors.

func reverse(in []rune) []rune {
    out := make([]rune, len(in))
    for i, v := range in {
        out[len(out)-i-1] = v
    return out

reverse() is a helper that Next() uses to copy one slice to another, reversing the order in the process.

func generate(from, to rune) []rune {
    list := make([]rune, 0, to-from+1)
    for itr := iutil.Range(int(from), int(to)+1); !itr.AtEnd(); itr.Next() {
        list = append(list, rune(itr.Int()))
    return list

generate() accepts paramters such as 'A', 'D' and returns a slice such as 'A','B','C','D'. It utilizes i.Range to generate an integer interval such as [63, 67) that is used to generate the rune slice.

    Permute(generate(from, to)),
    func(itr i.Iterator) bool {
        r, _ := itr.Value().([]rune)
        return true

The useage is the same as we've used to before, simply iterator through all possible permuations and print them out.
Get the source at GitHub.

No comments:

Post a Comment