Go言語で順列組み合わせ(Permutations and Combinations)

せっかくGo言語なのでchannelを使ってやってみた
sortパッケージみたいに、interfaceに対して関数を定義するのがGoっぽい？

リスト構造に新しいインデックスリスト[]intを渡して、
新しいリストを返すメソッドReplaceを作ると、

[a,b,c,d].Replace([]int{3,4,2,1,}) => [c,d,b,a]

[a,b,c,d].Replace([]int{1,4,1,}) => [a,d,a]

[]intに対して順列、組み合わせを列挙する関数さえ作れば、
上記interfaceに対しては、Replaceメソッドにそれを渡すだけでOK

順列も、組み合わせも、重複順列も、重複組み合わせも列挙できる

types.go

package listing

type Replacer interface {

	// Len() returns length
	// For example, return len([]string)
	Len() int

	// Replace([]int) returns a copy of Replacer that replaced new indices([]int)
	Replace([]int) Replacer
}

perm.go

package listing

//Permutation generator
func Permutations(list Replacer, select_num int, repeatable bool, buf int) (c chan Replacer) {
	c = make(chan Replacer, buf)
	go func() {
		defer close(c)
		var perm_generator func([]int, int, int) chan []int
		if repeatable {
			perm_generator = repeated_permutations
		} else {
			perm_generator = permutations
		}
		indices := make([]int, list.Len(), list.Len())
		for i := 0; i < list.Len(); i++ {
			indices[i] = i
		}
		for perm := range perm_generator(indices, select_num, buf) {
			c <- list.Replace(perm)
		}
	}()
	return
}

func pop(l []int, i int) (v int, sl []int) {
	v = l[i]
	length := len(l)
	sl = make([]int, length-1, length-1)
	copy(sl, l[:i])
	copy(sl[i:], l[i+1:])
	return
}

//Permtation generator for int slice
func permutations(list []int, select_num, buf int) (c chan []int) {
	c = make(chan []int, buf)
	go func() {
		defer close(c)
		switch select_num {
		case 1:
			for _, v := range list {
				c <- []int{v}
			}
			return
		case 0:
			return
		case len(list):
			for i := 0; i < len(list); i++ {
				top, sub_list := pop(list, i)
				for perm := range permutations(sub_list, select_num-1, buf) {
					c <- append([]int{top}, perm...)
				}
			}
		default:
			for comb := range combinations(list, select_num, buf) {
				for perm := range permutations(comb, select_num, buf) {
					c <- perm
				}
			}
		}
	}()
	return
}

//Repeated permtation generator for int slice
func repeated_permutations(list []int, select_num, buf int) (c chan []int) {
	c = make(chan []int, buf)
	go func() {
		defer close(c)
		switch select_num {
		case 1:
			for _, v := range list {
				c <- []int{v}
			}
		default:
			for i := 0; i < len(list); i++ {
				for perm := range repeated_permutations(list, select_num-1, buf) {
					c <- append([]int{list[i]}, perm...)
				}
			}
		}
	}()
	return
}

comb.go

package listing

//Combination generator
func Combinations(list Replacer, select_num int, repeatable bool, buf int) (c chan Replacer) {
	c = make(chan Replacer, buf)
	index := make([]int, list.Len(), list.Len())
	for i := 0; i < list.Len(); i++ {
		index[i] = i
	}

	var comb_generator func([]int, int, int) chan []int
	if repeatable {
		comb_generator = repeated_combinations
	} else {
		comb_generator = combinations
	}

	go func() {
		defer close(c)
		for comb := range comb_generator(index, select_num, buf) {
			c <- list.Replace(comb)
		}
	}()

	return
}

//Combination generator for int slice
func combinations(list []int, select_num, buf int) (c chan []int) {
	c = make(chan []int, buf)
	go func() {
		defer close(c)
		switch {
		case select_num == 0:
			c <- []int{}
		case select_num == len(list):
			c <- list
		case len(list) < select_num:
			return
		default:
			for i := 0; i < len(list); i++ {
				for sub_comb := range combinations(list[i+1:], select_num-1, buf) {
					c <- append([]int{list[i]}, sub_comb...)
				}
			}
		}
	}()
	return
}

//Repeated combination generator for int slice
func repeated_combinations(list []int, select_num, buf int) (c chan []int) {
	c = make(chan []int, buf)
	go func() {
		defer close(c)
		if select_num == 1 {
			for v := range list {
				c <- []int{v}
			}
			return
		}
		for i := 0; i < len(list); i++ {
			for sub_comb := range repeated_combinations(list[i:], select_num-1, buf) {
				c <- append([]int{list[i]}, sub_comb...)
			}
		}
	}()
	return
}

全ソースは以下に
https://github.com/kokardy/listing