電波ビーチ

☆(ゝω・)v

Goで順列を辞書順で

スライスのポインタで渡すところとスライスのコピーとスライスの任意のインデックスの要素を消すっていう実装が頭まわりませんでした…

実装

package main
import "fmt"

func main(){
    test := []int{1, 2, 3, 4}
    perms := permuration(test, 3)
    fmt.Println("1から4の中から3つ取る順列")
    fmt.Println(perms)

    // int以外の場合でもどうせインデックスを返すので数列を渡せばいい
    aquars := []string{"千歌", "梨子", "曜", "ダイヤ", "果南", "鞠莉", "善子", "花丸", "ルビィ"}
    indices := make([]int, len(aquars))
    for i := 0; i<len(aquars); i++{
        indices[i] = i
    }
    coupling := permuration(indices,  3)
    for _, c := range coupling{
        for i, v := range c{
            fmt.Print(aquars[v])
            if i<2{
                fmt.Print(" x ")
            }
        }
        fmt.Println()
    }
}

func permuration(target []int, limit int)([][]int){
    if limit<1 || len(target)<limit{
        return nil
    }
    ret := make([][]int, 0)
    gen_perm(make([]int, 0), target, &ret, limit)
    return ret
}

func gen_perm(perm []int, rest []int, lis *[][]int, n int){
    if n==0{
        *lis = append(*lis, perm)
    }else{
        // 探索
        for i, r := range rest{
            next_rest := make([]int, 0)
            next_rest = append(next_rest, rest...)
            next_perm := make([]int, 0)
            next_perm = append(next_perm, perm...)

            next_rest = deleteIndex(next_rest, i)
            next_perm = append(next_perm, r)
            gen_perm(next_perm, next_rest, lis, n-1)
        }

    }
}

func deleteIndex(in []int, index int)[]int{
    out := make([]int, 0)
    out = append(out, in...)
    if index<0 || len(in)<index{
        fmt.Println("delete index mis")
        return nil
    }
    out = append(out[:index], out[index+1:]...)
    return out
}

gen_perm は最初無名関数でやってたんですが無名関数の再帰ってできないんですね(当然)

参考

Go のスライスでハマッたところ - Block Rockin’ Codes

JavaScriptによる順列組み合わせの生成 - Qiita

http://antlers.cis.ibaraki.ac.jp/PROGRAM/CPROG/237.pdf