Go で 0 から始まる連続する n 個の整数を重複無く k 個選んだ時の組み合わせの列挙

問題がニッチ過ぎる気もしますが、Go言語で順列組み合わせ(Permutations and Combinations) - Qiitaにある通り、これを列挙できると任意の有限集合の組み合わせを列挙できます。

なぜ車輪の再発明をしたかといえば、非再帰的実装を思いついたからです(リンク先にあるcombinationsは再帰関数)。実用性とは関係無く、思いつきを形にしたくて実装しました。

下記コードはThe Go Playgroundで実行できます。

package main

import "fmt"

func main() {
    n := 6
    k := 4

    for xs := range CombinationInts(n, k) {
        fmt.Println(xs)
    }
}

func CombinationInts(n int, k int) <-chan []int {
    ch := make(chan []int)

    if 0 <= k && k <= n {
        go combInts(n, k, ch)
    } else {
        close(ch)
    }

    return ch
}

func combInts(n int, k int, ch chan<- []int) {
    defer close(ch)

    xs := makeFirstConb(n, k)
    sendCopy(xs, ch)

    for xs[0] < n-k {
        updateNextConb(xs, k)
        sendCopy(xs, ch)
    }
}

func makeFirstConb(n int, k int) []int {
    xs := make([]int, k+1)
    for i := range xs {
        xs[i] = i
    }
    xs[k] = n
    return xs
}

func updateNextConb(xs []int, k int) {
    for i := k - 1; i >= 0; i-- {
        if xs[i]+1 < xs[i+1] {
            xs[i]++

            for j := i + 1; j < k; j++ {
                xs[j] = xs[j-1] + 1
            }

            return
        }
    }
}

func sendCopy(xs []int, ch chan<- []int) {
    ys := make([]int, cap(xs)-1)
    copy(ys, xs[:len(xs)-1])
    ch <- ys
}