11

More than 5 years have passed since last update.

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

Posted at

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

リスト構造に新しいインデックスリスト[]intを渡して、

``````
[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に対して順列、組み合わせを列挙する関数さえ作れば、

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
}

``````

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
What you can do with signing up
11