Go でバックトラックを書いてみた

Go language に De Bruijn sequence を列挙するコードを移植してみました。C# で書いたときのコードは こ ち ら。
goroutine を使って並列化したいんですが、まだデッドロックしてうまくいってませんｗ なのでとりあえずできたシーケンシャル版。ちなみに効率的に列挙するコードじゃなく、いじめ試験みたいなものです。

De Bruijn の読みがずっと謎だったんですが、コンピュータの数学という本では「ドブリューイン」としてました。O記法の数学のあたりにちらっと名前が出てきました。

Go は関数から多値で返す文法がきれいでいいですね。C# の out はやってることは正しいのに、汚い文法なのが悲しい。レシーバーとインターフェイスでも遊んでみたいな。Go を最初に見たときは古臭い文法だと思ったけど、調べているといろいろと今どきっぽい機能をちゃんと持ってたりします。まーまだわからないことだらけですが。

package main

import (
    "math";
    "fmt";
    "os";
    "container/vector";
)

type DeBruijnSeq struct {
    k, n, max int;
    results *vector.Vector;
}

func Init( k, n int ) ( d *DeBruijnSeq, ok bool ) {
    if k < 2 || 10 < k { return nil, false }
    if n < 1 { return nil, false }

    pow := math.Pow( float64( k ), float64( n ) );
    if float64( 0x7FFFFFFF ) < pow { return nil, false }
    max := int( pow );

    r := vector.New( 0 );
    return &DeBruijnSeq{ k, n, max, r }, true
}

func ( d *DeBruijnSeq ) Search() {
    a := vector.NewIntVector( d.n );
    for i := 0; i < d.n; i++ { a.Set( i, 0 ) }
    d.searchCore( a );
}

func ( d *DeBruijnSeq ) searchCore( a *vector.IntVector ) {
    // 重複判定
    if !d.isUnique( a ) { return }

    // 完成判定
    if d.isComplete( a ) {
        d.output2( a );
        return
    }

    // 次の反復へ
    for i := 0; i < d.k; i++ {
        b := vector.NewIntVector( 0 );
        b.AppendVector( a );  // copy
        b.Push( i );
        d.searchCore( b );
    }
}

func ( d *DeBruijnSeq ) isUnique( a *vector.IntVector ) bool {
    if a.Vector.Len() <= d.n { return true }

    pos := a.Vector.Len() - d.n;

    for i := 0; i < pos; i++ {
        if sequenceEqual( a, i, pos, d.n ) { return false }
    }
    return true
}

func sequenceEqual( v *vector.IntVector, a, b, len int ) bool {
    for i := 0; i < len; i++ {
        if v.At( a ) != v.At( b ) { return false }
        a++; b++;
    }
    return true
}

func ( d *DeBruijnSeq ) isComplete( a *vector.IntVector ) bool {
    if a.Vector.Len() != d.max { return false }

    b := vector.NewIntVector( 0 );
    b.AppendVector( a );  // copy

    for i := 0; i < d.n - 1; i++ {
        b.Push( b.At( i ) );
        if !d.isUnique( b ) { return false }
    }
    return true
}

func ( d *DeBruijnSeq ) output2( a *vector.IntVector ) {
    d.results.Push( a )
}

func main() {
    d, ok := Init( 4, 2 );
    if !ok { os.Exit( 1 ); }

    d.Search();

    fmt.Println( d.results.Len() );

    if len := d.results.Len(); len < 10 {
        for i := 0; i < len; i++ {
            fmt.Println( d.results.At(i) )
        }
    }
}

VMware Player 上の x86 な Ubuntu に 2CPU 割り当てて実行したんですが、結構速いかも。