您的位置 首页 golang

用golang抄袭python的排列组合

为了处理数据,python用了一段时间,工具库多而全面。

相比之下,golang就少了许多,好多基础数据工具要自己实现。

由于语言特性,python一行代码,golang要付出好几个for循环才能实现。

查找了一圈,只找到了,五年前写的。功能没有写全,所以我fork了一个 ,先加上了组合的功能。

组合(python)

 def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)  

当我按照python的算法逻辑实现golang版本时候,也许是我算法能力太弱了,或者是对golang不够熟悉,始终没有找到能跟 python代码相媲美的写法。

组合(golang)

 func factorial(n int) int {
if n < 0 {
return 0
}
facVal := 1
for i := 1; i <= n ; i++  {
facVal *= i
}
return facVal
}
func Combinations(r int, els ... interface{}) (c []string){
pool := make([]string, 0)
//# combinations('ABCD', 2) --> AB AC AD BC BD CD
//# combinations(range(4), 3) --> 012 013 023 123
n := len(els)
if r >= n {
return nil
}
// 返回结果的总个数
m := factorial(n)/factorial(r)/factorial(n-r)
indices := make([]int, r)
indicesReverse := make([]int, r)
for i := 0; i < r; i++ {
indices[i] = i
indicesReverse[i] = i
}
for _, v := range els {
pool = append(pool, v.(string))
}
// 获取第一个
first := pool[indices[0]: r]
firstItem := strings.Join(first, ",")
c = append(c, firstItem)
sort.Sort(sort.Reverse(sort.IntSlice(indicesReverse)))
for {
if m <= len(c) {
return c
}
var i = 0
for ii := range indicesReverse {
i = indicesReverse[ii]
if indices[i] != i + n - r {
break
}
}
indices[i] += 1
var tmp []int
if i + 1 < r {
tmp = make([]int, r-(i+1))
var ti = 0
for tv := i+1; tv < r; tv++ {
tmp[ti] = tv
ti++
}
}
for _,j := range tmp {
indices[j] = indices[j - 1] + 1
}
var it []string
for _,v := range indices {
it = append(it, pool[v])
}
c = append(c, strings.Join(it, ","))
}
}  

单测

 package itertools

import (
"reflect"
"testing"
)
func TestCombinations(t *testing.T) {
cs := Combinations(3,"a","b","c","d", "e")
for c,vv := range cs {
//t := vv
println(c, vv)
}
}  

输出:

 0 a,b,c
1 a,b,d
2 a,b,e
3 a,c,d
4 a,c,e
5 a,d,e
6 b,c,d
7 b,c,e
8 b,d,e
9 c,d,e
PASS
ok      itertools       0.546s  

只能说自己写得不够好,等熟悉了之后再完善算法,后续会把python版本的itertools全部抄过来。

6月6号早上修复了bug,按照目前的算法,阶乘也就是m的数字必须计算精确,所以加上了factorial求阶乘的方法

文章来源:智云一二三科技

文章标题:用golang抄袭python的排列组合

文章地址:https://www.zhihuclub.com/97062.shtml

关于作者: 智云科技

热门文章

网站地图