全排列 & 任意排列 & 任意组合 & 笛卡尔积算法

排列和组合的区别：

排列：要求顺序，比如 [1,2] 和 [2,1] 是两个不同的排列
组合：不要求顺序，比如 [1,2] 和 [2,1] 是两个相同的组合

全排列：

给定n个数，返回长度为n的所有排列
比如 [1,2,3] 的全排列是 [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
可采用回溯法，遍历n叉树，得到所有路径

任意长度的排列：

给定n个数，返回任意长度的所有排列
比如 [1,2,3] 的任意长度的排列是 [[1] [1 2] [1 2 3] [1 3] [1 3 2] [2] [2 1] [2 1 3] [2 3] [2 3 1] [3] [3 1] [3 1 2] [3 2] [3 2 1]]
可采用回溯法，遍历n叉树，得到所有路径
和全排列的区别在于，路径长度可以为任意长度

组合：

给定n个数，和长度 m，返回长度为m的所有组合
比如 [1,2,3] 的长度为2的所有组合是 [[2 1] [3 1] [3 2]]
可想象为先从数组里取1个数，然后从剩余的 n-1 个数里取出 m-1 长度的所有组合，进而得到所有组合

笛卡尔积：

给定n个数组，每个数组取一个元素，返回长度为n的所有元素组合
比如 [[1, 2], [3, 4]] 的笛卡尔积是 [1, 3] [1 4] [2 3] [2 4]
比如 [[1, 2], [3, 4], [5, 6]] 的笛卡尔积是 [[1 3 5] [1 3 6] [1 4 5] [1 4 6] [2 3 5] [2 3 6] [2 4 5] [2 4 6]]
可采用递归计算方法，比如求解 n个数组的笛卡尔，可以递归求解 n-1 个数组的笛卡尔积，然后和第1个数组做2层for循环计算结果

代码如下

package main

import (
 "fmt"
)

func main() {
 var sol solution

 testCase := 3
 switch testCase {
 case 0: // 全排列
  sol.fullPermutation([]int{1, 2, 3}, nil)
  fmt.Println(sol.results)

 case 1: // 任意长度的排列
  sol.anyPermutation([]int{1, 2, 3}, nil)
  fmt.Println(sol.results)

 case 2: // 长度为n的组合
  fmt.Println(sol.combineN([]int{1, 2, 3}, 2))

 case 3: // 笛卡尔积
  fmt.Println(sol.crossJoin([][]int{
   []int{1, 2},
   []int{3, 4},
   []int{5, 6},
  }))
 }

 fmt.Println("Hello World")
}

type solution struct {
 results [][]int
}

/* 全排列组合，输入 [1,2,3]
返回 [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
*/
func (c *solution) fullPermutation(nums []int, path []int) {
 if len(path) == len(nums) {
  c.results = append(c.results, copyArray(path))
  return
 }

 for _, num := range nums { //选择列表
  if inArray(path, num) { //过滤不可以做的选择
   continue
  }

  path = append(path, num) //选择
  c.fullPermutation(nums, path)
  path = path[:len(path)-1] //取消选择
 }

 return
}

/* 任意长度的排列组合，输入 [1,2,3]
返回 [[1] [1 2] [1 2 3] [1 3] [1 3 2] [2] [2 1] [2 1 3] [2 3] [2 3 1] [3] [3 1] [3 1 2] [3 2] [3 2 1]]
*/
func (c *solution) anyPermutation(nums []int, path []int) {
 if len(path) > 0 { // path可以为任意长度
  c.results = append(c.results, copyArray(path))
 }
 if len(path) == len(nums) {
  return
 }

 for _, num := range nums { //选择列表
  if inArray(path, num) { //过滤不可以做的选择
   continue
  }

  path = append(path, num) //选择
  c.anyPermutation(nums, path)
  path = path[:len(path)-1] //取消选择
 }

 return
}

/* n个数字的所有组合（不要求顺序，需要去重），输入 [1,2,3]
返回 [[2 1] [3 1] [3 2]]
*/
func (c *solution) combineN(nums []int, n int) (results [][]int) {
 if n == 0 {
  return
 } else if n == 1 { // 当n=1时，每个数字都是一个组合，直接返回
  for _, num := range nums {
   results = append(results, []int{num})
  }
  return
 }
 if len(nums) == n { // 组合长度等于nums长度，直接返回 nums
  results = append(results, copyArray(nums))
  return
 }

 /*先取出第1个元素，然后在剩余的个元素中获取 n-1 长度的所有组合 */
 for i := 0; i <= len(nums)-n; i++ {
  subResults := c.combineN(nums[i+1:], n-1)
  for _, subRes := range subResults {
   res := copyArray(subRes)
   res = append(res, nums[i])
   results = append(results, res)
  }
 }
 return
}

/*笛卡尔积，输入 [[1, 2], [3, 4]]
返回 [1, 3] [1 4] [2 3] [2 4] */
func (c *solution) crossJoin(data [][]int) (results [][]int) {
 if len(data) == 0 {
  return
 } else if len(data) == 1 {
  results = data
  return
 }

 return getCrossJoin(data, 0)
}

func getCrossJoin(data [][]int, i int) (results [][]int) {
 if i == len(data)-1 {
  for _, num := range data[i] {
   results = append(results, []int{num})
  }
  return
 }

 subResults := getCrossJoin(data, i+1)

 for _, num := range data[i] {
  for _, subRes := range subResults {
   result := []int{num}
   result = append(result, subRes...)
   results = append(results, result)
  }
 }
 return
}

func inArray(nums []int, n int) bool {
 for _, num := range nums {
  if n == num {
   return true
  }
 }
 return false
}

func copyArray(nums []int) (copys []int) {
 copys = make([]int, len(nums))
 for i := range nums {
  copys[i] = nums[i]
 }
 return
}

全排列 & 任意排列 & 任意组合 & 笛卡尔积 算法

浏览过的版块

全排列 & 任意排列 & 任意组合 & 笛卡尔积算法