Go语言实现列出排列组合

今天,隔壁坐的小朋友给我一串数字:

1 6 21 55

让我观察规律,然后帮他推导公式。

尼玛,当我是神呢?!!

想了半天没看出个原委,

于是看了他那边具体需要才发现他那边是对N个数字进行5个数字的组合,

有多少种可能性的计算。

我一想,这不是初中学过的排列组合公式么。

显然,我忘记了,呵呵。

只记得大概是叫Pmn

然后通过搜索引擎看到如下百度百科里面排列组合的几十这里:

http://baike.baidu.com/item/%E6%8E%92%E5%88%97%E7%BB%84%E5%90%88/706498

Go语言实现列出排列组合

关键是当我用这个公式推导出上面数列里面的55是错的,应该是56.

小朋友不服啊!说他是一个一个手打出来检查过了的。

尼玛,不相信科学啊。

虽然他后面也相信这个公式了。

但是为了给他普及科学的强大,不要过分相信自己,也因为最近太闲,学得东西太杂,失去方向,于是就来练练Go语言吧。

我还是想办法去把这些排列组合打印粗来,代码写得难看,算法也是渣渣,但是勉强看吧:

 package main

 import (
"fmt"
"strconv"
"strings"
) var a []int = []int{, , , , , , }
var rawLen int
var combineLen int func main() {
rawLen = len(a)
combineLen =
combine()
} func combine() {
fmt.Println("start combine")
arrLen := len(a) - combineLen
for i := ; i <= arrLen; i++ {
result := make([]int, combineLen)
result[] = a[i]
//fmt.Println(i, arrLen)
doProcess(result, i, )
}
} func doProcess(result []int, rawIndex int, curIndex int) {
var choice int = rawLen - rawIndex + curIndex - combineLen
//fmt.Printf("Choice: %d, rawLen: %d, rawIndex : %d, curIndex : %d \r\n", choice, rawLen, rawIndex, curIndex)
var tResult []int
for i := ; i < choice; i++ {
if i != {
tResult := make([]int, combineLen)
copyArr(result, tResult)
} else {
tResult = result
}
//fmt.Println(curIndex)
tResult[curIndex] = a[i++rawIndex] if curIndex+ == combineLen {
PrintIntArr(tResult)
continue
} else {
doProcess(tResult, rawIndex+i+, curIndex+)
} }
} func copyArr(rawArr []int, target []int) {
for i := ; i < len(rawArr); i++ {
target[i] = rawArr[i]
}
} func PrintIntArr(arr []int) {
valuesText := []string{}
for i := range arr {
number := arr[i]
text := strconv.Itoa(number)
valuesText = append(valuesText, text)
} fmt.Println(strings.Join(valuesText, ","))
}

说明:

a:是用来组合的的所有数字,要保证他们的唯一性,不要出现重复的元素,不一定要保证顺序;

combineLen:需要组合成的长度

实现原理的关键点在这一句:

var choice int = rawLen - rawIndex + curIndex - combineLen

这句话的意思是什么呢?

此位置的可用种类 = 原始数组上都 - 原始数组里面当前循环到的位置索引 + 当前结果数组的索引 - 需要合成的数组的长度

啥意思呢?

怎么体会呢?

假设我们是长度为6的数组,我们要做成10个数字的组合,假设在循环原数组的第一个位置,索引为0的时候,我们目标数组的可选数有:

10 - 0 + 0 - 5 = 5

也就是0 - 5的索引即6中选择,在唯一元素的数组里面,你可以配合排序去理解,也就是:

0 1 2 3 4 5 6 7 8 9 

中第一个位置的可选是 0 1 2 3 4 5中选择,假设6,7,8,9可选,那么后面是无法补齐到5个数字的。

后面的任意索引都是以此类推。

以下结果是以5个元素3个数字进行组合的结果:

Go语言实现列出排列组合

这个故事告诉我们,程序行业还是要好好学习数学,最少得初中学历。

上一篇:RestFramework——API基本实现及dispatch基本源码剖析


下一篇:DevOps Workshop 研发运维一体化(成都站) 2016.05.08