Golang排列组合算法问题之全排列实现方法

silverwolf 发布于1年前 阅读18122次
0 条评论

本文实例讲述了Golang排列组合算法问题之全排列实现方法。分享给大家供大家参考,具体如下:

【排列组合问题】

一共N辆火车(0<N<10),每辆火车以数字1-9编号,要求以字典序排序输出火车出站的序列号。

输入:

包括N个正整数(0<N<10),范围为1到9,数字之间用空格分割,字符串首位不包含空格。

输出:

输出以字典序排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行。

样例输入:

1 2 3

样例输出:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

代码实现:

package huawei
 import (
     "fmt"
     "sort"
     "strings"
 )
 func Test7Base() {
     in := "5 2 3"
     result := outOrder(strings.Fields(in))
     dictSort(result)
     s := format(result)
     fmt.Println(s)
 }
 //输入trainsNums,返回全部排列
 //如输入[1 2 3],则返回[123 132 213 231 312 321]
 func outOrder(trainsNums []string) []string {
     COUNT := len(trainsNums)
     //检查
     if COUNT == 0 || COUNT > 10 {
         panic("Illegal argument. trainsNums size must between 1 and 9.")
     }
     //如果只有一个数,则直接返回
     if COUNT == 1 {
         return []string{trainsNums[0]}
     }
     //否则,将最后一个数插入到前面的排列数中的所有位置(递归)
     return insert(outOrder(trainsNums[:COUNT-1]), trainsNums[COUNT-1])
 }
 func insert(res []string, insertNum string) []string {
     //保存结果的slice
     result := make([]string, len(res)*(len(res[0])+1))
     index := 0
     for _, v := range res {
         for i := 0; i < len(v); i++ {
             //在v的每一个元素前面插入
             result[index] = v[:i] + insertNum + v[i:]
             index++
         }
         //在v最后面插入
         result[index] = v + insertNum
         index++
     }
     return result
 }
 //按字典顺序排序
 func dictSort(res []string) {
     sort.Strings(res)
 }
 //按指定格式输出
 func format(res []string) string {
     strs := make([]string, len(res))
     for i := 0; i < len(res); i++ {
         strs[i] = addWhiteSpace(res[i])
     }
     return strings.Join(strs, "\n")
 }
 //添加空格
 func addWhiteSpace(s string) string {
     var retVal string
     for i := 0; i < len(s); i++ {
         retVal += string(s[i])
         if i != len(s)-1 {
             retVal += " "
         }
     }
     return retVal
 }

需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。