投稿者: takatoh

Ruby の Array#repeated_combination は重複を許す組み合わせを返すメソッドだ（厳密にいうとEnumerator を返す）。
次のブログ記事で見つけた。

cf. 続：Haskell/Clojureでrepeated_combinationを実装してみる – Programmer’s Note

これを Go でやってみよう、ということで Haskell のコードを参考に作ってみた。

package main

import (
    "fmt"
)

func main() {
    xs := []int{ 1,2,3 }
    fmt.Println(repeatedCombination(xs, 3))
}

func repeatedCombination(xs []int, n int) [][]int {
    c := make([][]int, 0)
    if n == 1 {
        for _, x := range xs {
            c = append(c, []int{ x })
        }
    } else {
        for _, x := range xs {
            for _, y := range repeatedCombination(xs, n - 1) {
                c = append(c, append([]int{ x }, y...))
            }
        }
    }
    return c
}

ところが、実行結果が Array#repeated_combination と合わない。
上のコードの実行結果はこう。

^o^ > go run repeated_combination.go
[[1 1 1] [1 1 2] [1 1 3] [1 2 1] [1 2 2] [1 2 3] [1 3 1] [1 3 2] [1 3 3] [2 1 1] [2 1 2] [2 1 3] [2 2 1] [2 2 2] [2 2 3] [2 3 1] [2 3 2] [2 3 3] [3 1 1] [3 1 2] [3 1 3] [3 2 1] [3 2 2] [3 2 3] [3 3 1] [3 3 2] [3 3 3]]

対して Array#repeated_combination はこう。

irb(main):001:0> [1,2,3].repeated_combination(3).to_a
=> [[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]]

順列ではなく組み合わせなので、Array#repeated_combination では例えば [1,1,2] と [1,2,1] と [2,1,1] を同じものとしているのに対して、Go のコードでは別のものとして数え上げてしまっている。
そこで改良を加えたのがこれだ。

package main

import (
    "fmt"
)

func main() {
    xs := []int{ 1,2,3 }
    fmt.Println(repeatedCombination(xs, 3))
}

func repeatedCombination(xs []int, n int) [][]int {
    c := make([][]int, 0)
    if n == 1 {
        for _, x := range xs {
            c = append(c, []int{ x })
        }
    } else {
        for _, x := range xs {
            for _, y := range repeatedCombination(xs, n - 1) {
                if x <= y[0] {
                    c = append(c, append([]int{ x }, y...))
                }
            }
        }
    }
    return c
}

実行結果。

^o^ > go run repeated_combination2.go
[[1 1 1] [1 1 2] [1 1 3] [1 2 2] [1 2 3] [1 3 3] [2 2 2] [2 2 3] [2 3 3] [3 3 3]]

今度はうまくいった。

最近見かけたブログの記事。

cf. Haskell/Clojureで数学パズル：コインの両替 – Programmer’s Note

同じような問題はずっと前に Haskell でやったことがあるんだけど、今回は Go でやってみる。はじめに思い付いたのはリンク記事の後半に出てくる再帰を使ったほうなんだけど、まずはリンク記事と同じ順で for を使ったやり方で。

package main

import (
    "fmt"
)

func main() {
    fmt.Println(change_coin(1000, 15))
}

func change_coin(money, max_coins int) int {
    patterns := 0
    for m10 := 0; m10 <= max_coins; m10++ {
        for m50 := 0; m50 <= max_coins; m50++ {
            for m100 := 0; m100 <= max_coins; m100++ {
                for m500 := 0; m500 <= max_coins; m500++ {
                    if m10 + m50 + m100 + m500 <= max_coins && 10 * m10 + 50 * m50 + 100 * m100 + 500 * m500 == money {
                        patterns += 1
                    }
                }
            }
        }
    }
    return patterns
}

ああ、ネストした for 文が美しくない!!

で、こっちが再帰を使ったほう。

package main

import (
    "fmt"
)

func main() {
    coins := []int{ 10, 50, 100, 500 }
    fmt.Println(change_coin2(1000, coins, 15))
}

func change_coin2(money int, coins []int, max_coins int) int {
    if money == 0 {
        return 1
    } else if len(coins) == 0 {
        return 0
    } else if max_coins == 0 {
        return 0
    } else {
        patterns := 0
        for use := 0; use <= max_coins; use++ {
            patterns += change_coin2(money - coins[0] * use, coins[1:], max_coins - use) } return patterns
    }
}

だいぶマシだけど else if がなあ。改めて Haskell のパターンマッチの美しいことを思い知る。

ゴルーチンとチャネルを使ってジェネレータを作ることもできる。

package main

import (
    "fmt"
)

type Item interface {
    Eq(Item) bool
    Less(Item) bool
}

type Node struct {
    item Item
    left, right *Node
}

func newNode(x Item) *Node {
    p := new(Node)
    p.item = x
    return p
}

func insertNode(node *Node, x Item) *Node {
    switch {
        case node == nil: return newNode(x)
        case x.Eq(node.item): return node
        case x.Less(node.item): node.left = insertNode(node.left, x)
        default: node.right = insertNode(node.right, x)
    }
    return node
}

func foreachNode(f func(Item), node *Node) {
    if node != nil {
        foreachNode(f, node.left)
        f(node.item)
        foreachNode(f, node.right)
    }
}

type Tree struct {
    root *Node
}

func newTree() *Tree {
    return new(Tree)
}

func (t *Tree) insertTree(x Item) {
    t.root = insertNode(t.root, x)
}

func (t *Tree) foreachTree(f func(Item)) {
    foreachNode(f, t.root)
}

func (t *Tree) makeGen() func() Item {
    ch := make(chan Item)
    go func() {
        t.foreachTree(func(x Item) {
            ch <- x }
        )
        close(ch)
    }()
    return func() Item {
        return <- ch
    }
}

type Int int

func (n Int) Eq(m Item) bool {
    return n == m.(Int)
}

func (n Int) Less(m Item) bool {
    return n < m.(Int)
}

func main() {
    a := newTree() b := []int { 5,6,4,7,3,8,2,9,1,0 }
    for _, x := range b {
        a.insertTree(Int(x))
    }
    resume := a.makeGen()
    for i := 0; i < 11; i++ {
        fmt.Println(resume())
    }
}

makeGen 関数は無名関数を返す。この無名関数はクロージャになっていて、makeGen 内のゴルーチンからチャネルを使って受け取った値を返す。ゴルーチンは二分木の値を昇順に返すので、結果として無名関数も呼び出しごとに同じ順で値を返すことになる。
実行してみよう。

^o^ > go run go_gen.go
0
1
2
3
4
5
6
7
8
9
<nil>

最後の <nil> は何だろう？

チャネルから送られてくるデータは、for ループの range で受けることもできる。

for v := チャネル { 処理 }

チャネルの場合、スライスやマップと違って返り値は多値ではない。あと、チャネルにデータを送る側では、送信が終わったらチャネルを close する必要がある。
次の例は、二分木にチャネルを使ってデータを送信する each 関数を追加したものだ。

package main

import (
    "fmt"
)

type Item interface {
    Eq(Item) bool
    Less(Item) bool
}

type Node struct {
    item Item
    left, right *Node
}

func newNode(x Item) *Node {
    p := new(Node)
    p.item = x
    return p
}

func insertNode(node *Node, x Item) *Node {
    switch {
        case node == nil: return newNode(x)
        case x.Eq(node.item): return node
        case x.Less(node.item):
            node.left = insertNode(node.left, x)
        default:
            node.right = insertNode(node.right, x)
    }
    return node
}

func foreachNode(f func(Item), node *Node) {
    if node != nil {
        foreachNode(f, node.left)
        f(node.item)
        foreachNode(f, node.right)
    }
}

type Tree struct {
    root *Node
}

func newTree() *Tree {
    return new(Tree)
}

func (t *Tree) insertTree(x Item) {
    t.root = insertNode(t.root, x)
}

func (t *Tree) foreachTree(f func(Item)) {
    foreachNode(f, t.root)
}

func (t *Tree) each() chan Item {
    ch := make(chan Item)
    go func() {
        t.foreachTree(func(x Item) { ch <- x })
        close(ch)
    }()
    return ch
}

type Int int

func (n Int) Eq(m Item) bool {
    return n == m.(Int)
}

func (n Int) Less(m Item) bool {
    return n < m.(Int)
}

func main() {
    a := newTree() b := []int { 5,6,4,3,7,8,2,1,9,0 }
    for _, x := range b {
        a.insertTree(Int(x))
    }
    for x := range a.each() {
        fmt.Println(x)
    }
}

for ループの range には二分木の each 関数を呼び出していて、その each 関数では、データを一つずつチャネルに送信し、最後にチャネルを close している。
実行結果はこう：

^o^ > go run go_range.go
0
1
2
3
4
5
6
7
8
9

チャネルを使ってゴルーチンの同期をとることができる。
次のコードを見てほしい。

package main

import (
    "fmt"
    "time"
)

func makeRoutine(code string, in <-chan int) chan int {
    out := make(chan int)
    go func() {
        for {
            <- in fmt.Print(code)
            time.Sleep(200 * time.Millisecond) out <- 0
        }
    }()
    return out
}

func main() {
    ch1 := make(chan int)
    ch2 := makeRoutine("h", ch1)
    ch3 := makeRoutine("e", ch2)
    ch4 := makeRoutine("y", ch3)
    ch5 := makeRoutine("!", ch4)
    ch6 := makeRoutine(" ", ch5)
    for i := 0; i < 10; i++ {
        ch1 <- 0 <- ch6
    }
}

makeRoutine 関数は、文字列 code とチャネル in を引数にとる。まずチャネル out を作っておいて、無名関数をゴルーチンで起動、最後に out を返している。無名関数は無限ループになっていて、in から何か送信されてくるのを待って code を出力し、200 ミリ秒待ってから out にデータを送信する。
main 関数では、最初の（送信用）チャネル ch1 を作り、makeRoutine 関数に渡している。返ってきたチャネルは、次の makeRoutine 関数に渡され、返ってきたチャネルはさらに次の makeRoutine 関数に渡される。こうして5つの makeRoutine 関数の中のゴルーチンがチャネルを通じて数珠つなぎのようになる。これらのゴルーチンは、最初のチャネル ch1 にデータを送信することによって動作を開始し、最後のチャネル（main 関数から見ると ch6）にデータを送信して終わる。これを10回繰り返している。

実行してみよう。

^o^ > go run go_hey.go
hey! hey! hey! hey! hey! hey! hey! hey! hey! hey!

この実行例ではわからないけど、1文字ずつ時間を空けて hey! の文字列が10回出力されている。各ゴルーチンは1文字出力するだけなので、うまく同期して動作している様子がわかる。

ゴルーチンの終了待ちには、チャネルを使うほかに sync パッケージの WaitGroup を使う方法もある。
使い方はこうだ：

1. sync.WaitGroup の変数を作る
2. その変数に、終了待ちをするゴルーチンの数を設定する
3. ゴルーチンを呼び出す。このとき、sync.WaitGroup の変数を渡す
4. ゴルーチン側では、終了したら Done 関数を呼ぶ
5. メインルーチン側で、Wait 関数を呼ぶ

実際に試してみよう。

package main

import (
    "fmt"
    "time"
    "sync"
)

func test(n int, name string, wg *sync.WaitGroup) {
    for i := 0; i < n; i++ {
        fmt.Println(i, name)
        time.Sleep(500 * time.Millisecond)
    }
    wg.Done()
}

func main() {
    var wg sync.WaitGroup wg.Add(3)
    go test(6, "foo", &wg)
    go test(4, "bar", &wg)
    go test(8, "baz", &wg) wg.Wait()
}

^o^ > go run go_waitgroup.go
0 baz
0 bar
0 foo
1 baz
1 bar
1 foo
2 baz
2 bar
2 foo
3 baz
3 bar
3 foo
4 baz
4 foo
5 baz
5 foo
6 baz
7 baz

チャネルはゴルーチンの間で通信するためのデータだ。次のように生成する。

ch := make(chan T, bufsize)

T はチャネルでやり取りするデータの型、bufsize はデータを格納するバッファのサイズで省略すると 0 になる。チャネルの型は chan T。
関数の引数や変数の型指定の時、chan の前に <- をつけると受信専用に、後に <- をつけると送信専用になる。 チャネルを使うと、ゴルーチンの終了待ちができるようになる。 次の例では test 関数をゴルーチンとして呼び出し、チャネルを渡している。test 関数は 0.5 秒間隔で name を出力し、終了するときにチャネルを通じて name を送ってくる。main 関数ではチャネルからデータが送られてくるのを待っている。

package main

import (
    "fmt"
    "time"
)

func test(n int, name string, c chan<- string) {
    for i := 1; i <= n; i++ {
        fmt.Println(i, name)
        time.Sleep(500 * time.Millisecond)
    }
    c <- name
}

func main() {
    c := make(chan string)
    go test(6, "foo", c)
    go test(4, "bar", c)
    go test(8, "baz", c)
    for i := 0; i < 3; i++ {
        name := <- c fmt.Println(name)
    }
}

実行してみよう。

^o^ > go run go_channel.go
1 foo
1 baz
1 bar
2 foo
2 baz
2 bar
3 foo
3 baz
3 bar
4 foo
4 baz
4 bar
5 foo
5 baz
bar
6 foo
6 baz
foo
7 baz
8 baz
baz

数字とともに出力されているのが test 関数内で出力したもの、数字のないのがゴルーチンが終了した後に main 関数で出力したものだ。3つのゴルーチンが並行して動き、main 関数ではその終了を待っていることがわかる。

Go でスライスを逆順にしたかったんだけど、そういう関数は用意されてないようだ。じゃあどうするかというと for 文を使ってひとつずつ入れ替えてくしかないみたい。こんなふうに。

package main

import (
    "fmt"
)

func main() {
    s := []int{ 1,2,3,4,5 }
    for i, j := 0, len(s) - 1; i < j; i, j = i + 1, j - 1 {
        s[i], s[j] = s[j], s[i]
    }
    fmt.Println(s)
}

^o^ > go run reverse.go
[5 4 3 2 1]

文字列を逆順にするにはいったん rune 型のスライスにしてから。

package main

import (
    "fmt"
)

func main() {
    s := "あいうえお"

    runes := []rune(s)
    for i, j := 0, len(runes) - 1; i < j; i, j = i + 1, j - 1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    fmt.Println(string(runes))
}

^o^ > go run reverse_string.go
おえういあ