Golang递归实现排列组合计算

Golang递归实现排列组合计算 https://play.golang.org/p/cS7S3tYAXrn

递归函数 permute() 在处理包含6个唯一整数的切片时可以正常工作，但在处理7个或更多整数时会失败。

我哪里出错了？

代码复制如下：

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// 递归函数，返回给定输入（[]int）的所有可能排列
func permute(prefix []int, input []int) [][]int {
	if len(input) == 0 {
		return [][]int{prefix}
	}
	// fmt.Println("permute", prefix, input)
	var res [][]int
	for i := range input {
		// cc := copy(input)
		cc := make([]int, len(input))
		copy(cc, input) // 内置函数
		if i > 0 {
			cc[0], cc[i] = cc[i], cc[0]
		}
		newprefix := append(prefix, cc[0])
		p := permute(newprefix, cc[1:])
		res = append(res, p...)
		// fmt.Println("  append", prefix, p)
	}
	// fmt.Println("  res", prefix, res)
	return res
}

// 使用映射来计算每个排列的出现次数
// 输入：排列的切片（[][]int）
func checkdup(input [][]int) {
	m := make(map[string]int)
	for _, n := range input {
		var s []string
		for _, i := range n {
			s = append(s, strconv.Itoa(i))
		}
		key := strings.Join(s, "-")
		m[key]++
	}
	fmt.Printf("%d in the map, %d unique\n", len(input), len(m))
}

// 返回 n 的阶乘
func factorial(n int) int {
	i := n
	for i > 1 {
		i--
		n = n * i
	}
	return n
}

func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7}
	fmt.Println("permute 6 (6! is", factorial(6), ")")
	p = permute(nil, a[:6])
	checkdup(p)
	fmt.Println("permute 7 (7! is", factorial(7), ")")
	p = permute(nil, a[:7])
	checkdup(p)
}

更多关于Golang递归实现排列组合计算的实战教程也可以访问 https://www.itying.com/category-94-b0.html

5 回复

哇，谢谢！非常感谢您的解释和提供的链接！

更多关于Golang递归实现排列组合计算的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


我需要补充一点，当给定7个整数时，我期望得到5040个唯一的排列，但我只得到了这个数字的一半；每个返回的排列都是重复的。

有趣的事实：

对于7个整数，观察到的排列数量是预期数量的一半。 对于8个整数，观察到的数量是预期数量的六分之一。 对于9个整数和10个整数，结果又恢复正常了。

permute 6 (6! is 720)
720 in the map, 720 unique
permute 7 (7! is 5040)
5040 in the map, 2520 unique
permute 8 (8! is 40320)
40320 in the map, 6720 unique
permute 9 (9! is 362880)
362880 in the map, 362880 unique
permute 10 (10! is 3628800)
3628800 in the map, 3628800 unique

（也许这对故障排除有帮助，但我太累了，无法深入探究。）

问题在于

newprefix = append(prefix, cc[0])

这段代码可以正常工作：

newprefix := make([]int, len(prefix)+1)
copy(newprefix, prefix)
newprefix = append(newprefix, cc[0])

根据经验法则，append 应该仅用于向给定切片追加值，而不应在同一操作中用于创建新切片。

这个问题的根源在于 append 如何影响底层数组。append 可能会就地修改数组，或者如果容量不足，则会创建一个新数组，将旧数组复制过去，然后开始在那里追加。

关于就地修改与追加的基本流程，请参见此处（在 append() 部分）。

当 append 返回值的接收者与传递给 append 的切片不是同一个时，这个流程可能导致意外行为。

这个 StackOverflow 回答建议了一个结合 copy 和 append 的函数：

func copyAndAppend(i []int, vals ...int) []int {
    j := make([]int, len(i), len(i)+len(vals))
    copy(j, i)
    return append(j, vals...)
}

问题在于递归算法中的切片操作导致了重复排列。当输入切片长度超过6时，permute函数中的cc[1:]操作会与原始切片共享底层数组，导致后续迭代中数据被意外修改。

以下是修复后的代码：

package main

import (
	"fmt"
	"strconv"
	"strings"
)

func permute(prefix []int, input []int) [][]int {
	if len(input) == 0 {
		return [][]int{prefix}
	}
	
	var res [][]int
	for i := range input {
		// 创建新的输入切片副本
		newInput := make([]int, len(input))
		copy(newInput, input)
		
		// 交换元素位置
		newInput[0], newInput[i] = newInput[i], newInput[0]
		
		// 创建新的前缀切片
		newPrefix := make([]int, len(prefix))
		copy(newPrefix, prefix)
		newPrefix = append(newPrefix, newInput[0])
		
		// 递归处理剩余元素
		p := permute(newPrefix, newInput[1:])
		res = append(res, p...)
	}
	return res
}

func checkdup(input [][]int) {
	m := make(map[string]int)
	for _, n := range input {
		var s []string
		for _, i := range n {
			s = append(s, strconv.Itoa(i))
		}
		key := strings.Join(s, "-")
		m[key]++
	}
	fmt.Printf("%d in the map, %d unique\n", len(input), len(m))
}

func factorial(n int) int {
	result := 1
	for i := 2; i <= n; i++ {
		result *= i
	}
	return result
}

func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7}
	
	fmt.Println("permute 6 (6! is", factorial(6), ")")
	p := permute(nil, a[:6])
	checkdup(p)
	
	fmt.Println("permute 7 (7! is", factorial(7), ")")
	p = permute(nil, a[:7])
	checkdup(p)
}

关键修复点：

  1. 在每次递归调用前创建newPrefix的完整副本，避免共享底层数组
  2. 修复了阶乘函数的实现
  3. 确保所有切片操作都使用新的底层数组

运行结果将正确显示：

permute 6 (6! is 720 )
720 in the map, 720 unique
permute 7 (7! is 5040 )
5040 in the map, 5040 unique
回到顶部