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
}