您的位置 首页 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

关于作者: 智云科技

热门文章

网站地图