Golang 计算字符串所有排列

在Go编程语言中，字符串是内置的数据类型，表示字符序列。它们使用双引号(“)定义，并可以包含任何有效的Unicode字符。字符串的排列是具有相同字符但不同字符顺序的唯一字符串。例如，单词”abcd”和”dabc”是彼此的排列组合。在这个程序中，我们将探讨找到字符串排列的方法，并使用Golang中的打印语句在控制台上打印输出。

语法

func append(slice, element_1, element_2…, element_N) []T

append 函数用于向数组切片中添加值。它接受多个参数。第一个参数是我们希望向其添加值的数组，接着是要添加的值。函数然后返回包含所有值的最终数组切片。

func len(v Type) int

len() 函数用于获取任何参数的长度。它接受一个参数作为数据类型变量，我们希望找到其长度，并返回整数值，即变量的长度。

步骤

步骤1 - 在主程序中创建一个main 包，并声明 fmt（格式化包） package，其中 main 产生可执行示例，fmt 则用于格式化输入和输出。
步骤2 - 通过 main 函数，将输入列表、其长度以及包含排列的整数切片数组的指针传递给 heapPermutation 函数。
步骤3 - heapPermutation 函数验证列表的长度是否为 1。如果是，则我们已经固定了列表的所有元素，使当前列表成为一个排列。因此，它将当前列表添加到排列切片中。
步骤4 - 如果列表的长度大于 1，则函数进入一个循环，在该循环中它连续使用列表的 n-1 个条目调用自身。
步骤5 - 在循环中，使用嵌套循环将列表的最后一个元素与其前面的每个元素进行交换。
步骤6 - 然后，该函数通过将当前排列添加到排列切片中来保存当前排列。
步骤7 - 函数接着使用 if 语句确定列表的长度是奇数还是偶数。如果是奇数，则将第一个元素与最后一个元素交换；如果是偶数，则将第 i 个索引处的元素与最后一个元素交换。
步骤8 - 在此之后，函数针对列表中的每个元素重复上述过程。
步骤9 - 在生成所有可能的排列之后，函数返回排列切片。
步骤10 - 使用 fmt.Println() 函数在控制台上打印排列，其中 ln 表示换行。
步骤11 - 这种方法的时间复杂度为O(n!)，因为对于长度为n的列表，有n!个排列。由于所有排列都必须存储在切片中，所以空间复杂度也是O(n!)。由于其非递归性质，该策略对于大型输入可能比递归方法更有效，因为它避免了堆栈溢出错误。

示例

这里我们使用 Heap 算法来创建给定列表的按字典顺序排序的所有排列。

package main
import (
   "fmt"
)

func heapPermutation(mystr []int, n int, permutations *[][]int) {
   if n == 1 {
      *permutations = append(*permutations, append([]int{}, mystr...))
      return
   }
   for i := 0; i < n; i++ {   //calculate the permutation using heap
      heapPermutation(mystr, n-1, permutations)
      if n%2 == 0 {
         mystr[i], mystr[n-1] = mystr[n-1], mystr[i]
      } else {
         mystr[0], mystr[n-1] = mystr[n-1], mystr[0]
      }
   }
}

func main() {
   mystr := []int{10, 20, 30}  //create a slice with numbers whose permutation is to be calculated 
   fmt.Println("The elements of string are:", mystr)
   permutations := [][]int{}
   heapPermutation(mystr, len(mystr), &permutations)
   fmt.Println("The permutations of string presented here is:")
   fmt.Println(permutations)  //print the permutations 
}

输出

The elements of string are: [10 20 30]
The permutations of string presented here is:
[[10 20 30] [20 10 30] [30 10 20] [10 30 20] [20 30 10] [30 20 10]]