Go语言生成0..n-1的长度k子序列时出现重复序列问题

问题根源 #

你的动态规划代码中存在切片浅拷贝导致的引用共享问题，当数据规模变大（比如n=43、k=5）时，这种问题会触发重复序列的生成：

• 代码中curr := append([][]int{}, H[i-1][j-1]...)只是对二维切片做了浅拷贝，curr里的每个元素仍然指向H[i-1][j-1]中切片的底层数组。
• 后续curr[y] = append(curr[y],i)会直接修改原切片的底层数组，导致之前已经存入H中的序列被意外修改，最终出现重复。
• 小数据量时，底层数组的扩容机制可能暂时掩盖了这个问题，但数据量增大后，引用冲突就会显现。

修复后的代码 #

修改核心逻辑，对每个子序列做深拷贝，避免引用共享：

func genSequences(n int, k int) [][]int {
    // 初始化DP表，H[i][j]表示0~i中长度为j+1的所有子序列（j从0开始）
    H := make([][][][]int, n)
    for i := range H {
        H[i] = make([][][]int, n)
    }

    H[0][0] = [][]int{{0}}
    // 初始化长度为1的子序列（j=0）
    for i := 1; i < n; i++ {
        H[i][0] = append(H[i-1][0], []int{i})
    }
    // 初始化长度为j+1的连续子序列（i=j）
    for j := 1; j < k; j++ {
        prevSeq := make([]int, len(H[j-1][j-1][0]))
        copy(prevSeq, H[j-1][j-1][0])
        H[j][j] = [][]int{append(prevSeq, j)}
    }

    for j := 1; j < k; j++ {
        for i := j + 1; i < n; i++ {
            curr := make([][]int, len(H[i-1][j-1]))
            // 对每个子序列做深拷贝，再追加i
            for y := range H[i-1][j-1] {
                temp := make([]int, len(H[i-1][j-1][y]))
                copy(temp, H[i-1][j-1][y])
                curr[y] = append(temp, i)
            }
            // 合并之前的结果和新生成的序列
            H[i][j] = append(append([][]int{}, H[i-1][j]...), curr...)
        }
    }

    return H[n-1][k-1]
}

关键修改点 #

• 初始化H[j][j]时，不再直接append(H[j-1][j-1][0], j)，而是先拷贝原序列到新切片，再追加元素。
• 生成curr时，对H[i-1][j-1]中的每个子序列都创建新切片并拷贝内容，避免修改原数据。
• 合并H[i][j]时，先浅拷贝H[i-1][j]的内容，再追加新生成的curr，防止后续修改影响之前的结果。

验证 #

用你的测试代码运行修复后的genSequences(43,5)，控制台会输出true，说明重复序列问题已解决。

内容的提问来源于stack exchange，提问作者ajgateno