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