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

本文实例讲述了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
}

希望本文所述对大家Go语言程序设计有所帮助。

赞 (0)

相关推荐

  • Go语言如何并发超时处理详解

    实现原理: 并发一个函数,等待1s后向timeout写入数据,在select中如果1s之内有数据向其他channel写入则会顺利执行,如果没有,这是timeout写入了数据,则我们知道超时了. 实现代码: package main import "fmt" import "time" func main() { ch := make(chan int, 1) timeout := make(chan bool, 1) // 并发执行一个函数,等待1s后向timeou

  • go语言文件正则表达式搜索功能示例

    本文实例讲述了go语言文件正则表达式搜索功能.分享给大家供大家参考,具体如下: 复制代码 代码如下: package main import (     "fmt"     "os"     "path/filepath"     "regexp" ) func main() {     // 命令行参数     args := os.Args     // 检查参数     if len(args) == 1 {      

  • Go语言实现的排列组合问题实例(n个数中取m个)

    本文实例讲述了Go语言实现的排列组合问题.分享给大家供大家参考,具体如下: (一)组合问题 组合是一个基本的数学问题,本程序的目标是输出从n个元素中取m个的所有组合. 例如从[1,2,3]中取出2个数,一共有3中组合:[1,2],[1,3],[2,3].(组合不考虑顺序,即[1,2]和[2,1]属同一个组合) 本程序的思路(来自网上其他大神): (1)创建有n个元素数组,数组元素的值为1表示选中,为0则没选中. (2)初始化,将数组前m个元素置1,表示第一个组合为前m个数. (3)从左到右扫描数

  • GO语言运行环境下载、安装、配置图文教程

    GO语言运行环境下载、安装、配置图文教程

    一.Go语言下载 go语言官方下载地址:https://golang.org/dl/ 找到适合你系统的版本下载,本人下载的是windows版本.也可以下载Source自己更深层次研究go语言. 二.GO语言安装 下载完成之后,双击go1.6.windows-amd64.msi进行安装. 如果安装过程出现以下提示: 以管理员的身份运行cmd,找到go1.6.windows-amd64.msi所在的目录,并输入msiexec /i go1.6.windows-amd64.msi如下图(放在D盘根目录

  • Go语言正则表达式用法实例小结【查找、匹配、替换等】

    本文实例讲述了Go语言正则表达式用法.分享给大家供大家参考,具体如下: Go语言的正则表达式使用很简单,示例代码: 复制代码 代码如下: package test import (     "fmt"     "regexp" ) func RegixBase() {     //findTest()     //findIndexTest()     //findStringTest()     //findChinesString()     //findNum

  • 利用Go语言实现简单Ping过程的方法

    利用Go语言实现简单Ping过程的方法

    一.准备工作 安装最新的Go 1.由于Google被墙的原因,如果没有VPN的话,就到这里下载:http://www.golangtc.com/download 2.使用任意文本编辑器,或者LiteIDE会比较方便编译和调试 二.编码 要用到的package: import ( "bytes" "container/list" "encoding/binary" "fmt" "net" "os&q

  • Go语言中三种不同md5计算方式的性能比较

    前言 本文主要介绍的是三种不同的 md5 计算方式,其实区别是读文件的不同,也就是磁盘 I/O, 所以也可以举一反三用在网络 I/O 上.下面来一起看看吧. ReadFile 先看第一种, 简单粗暴: func md5sum1(file string) string { data, err := ioutil.ReadFile(file) if err != nil { return "" } return fmt.Sprintf("%x", md5.Sum(dat

  • Go语言中反射的正确使用

    介绍 反射是元数据编程的一种形式,指的是程序获得本身结构的一种能力.不同语言的反射模型实现不一样,本文中的反射,仅仅指的是Go语言中的反射模型. 反射有两个问题,在使用前需要三思: 大量的使用反射会损失一定性能 Clear is better than clever. Reflection is never clear. Go的类型设计上有一些基本原则,理解这些基本原则会有助于你理解反射的本质: 变量包括 <type, value> 两部分.理解这一点你就知道为什么nil != nil了. t

  • Go语言对字符串进行SHA1哈希运算的方法

    本文实例讲述了Go语言对字符串进行SHA1哈希运算的方法.分享给大家供大家参考.具体如下: 复制代码 代码如下: package main import (  "fmt"  "crypto/md5"  "crypto/sha1"  "io" ) //对字符串进行MD5哈希 func a(data string) string {  t := md5.New();  io.WriteString(t,data);  return

  • PHP与Go语言之间的通信详解

    前言 最近工作中遇到的一个场景,php项目中需要使用一个第三方的功能,而恰好有一个用Golang写好的类库.那么问题就来了,要如何实现不同语言之间的通信呢?下面就来一起看看吧. 常规的方案 1. 用Golang写一个http/TCP服务,php通过http/TCP与Golang通信 2.将Golang经过较多封装,做为php扩展. 3.PHP通过系统命令,调取Golang的可执行文件 存在的问题 1.http请求,网络I/O将会消耗大量时间 2.需要封装大量代码 3.PHP每调取一次Golang

  • 深入理解GO语言的面向对象

    前言 有过C++语言学习经历的朋友都知道,面向对象主要包括了三个基本特征:封装.继承和多态.封装,就是指运行的数据和函数绑定在一起,C++中主要是通过this指针来完成的:继承,就是指class之间可以相互继承属性和函数:多态,主要就是用统一的接口来处理通用的逻辑,每个class只需要按照接口实现自己的回调函数就可以了. 作为集大成者的Go语言,自然不会在面向对象上面无所作为.相比较C++.Java.C#等面向对象语言而言,它的面向对象更简单,也更容易理解. go语言中并没有像C++,Java语

随机推荐