doumiyi7063 2019-02-25 04:30
浏览 32
已采纳

golang组合生成出错

I'm dealing with a programming problem

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

and with input n = 5, k = 4, the output should be [[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]], the following is my golang solution

func combine(n int, k int) [][]int {
    result := [][]int{}
    comb := []int{}
    subcom(0, k, n, &comb, &result)
    return result
}

func subcom(s, k, n int, comb *[]int, result *[][]int) {
    if k > 0 {
        for i := s + 1; i <= n-k+1; i++ {
            c := append(*comb, i)
            subcom(i, k-1, n, &c, result)
        }
    } else {
        *result = append(*result, *comb)
    }
}

I think my solution is right, but it return [[1 2 3 5] [1 2 3 5] [1 2 4 5] [1 3 4 5] [2 3 4 5]].

After debugging, I found [1 2 3 4] was added to the result slice at the beginning, but later changed to [1 2 3 5], resulting in the repetition of two [1 2 3 5]s. But I can't figure out what's wrong here.

  • 写回答

1条回答 默认 最新

  • dse84825 2019-02-25 04:52
    关注

    This is a common mistake when using append.

    When your code runs c:=append(*comb,i), it tries to first use the allocated memory in the underlying array to add a new item and only create a new slice when it failed to do so. This is what changes the [1 2 3 4] to [1 2 3 5] - because they share the same underlying memory.

    To fix this, copy when you want to append into result:

    now := make([]int,len(*comb))
    copy(now,*comb)
    *result = append(*result,now)
    

    Or use a shortcut of copying:

    *result = append(*result, append([]int{},*comb...))
    

    Update:

    To understand what I mean by underlying memory, one should understandd the internal model of Go's slice.

    In Go, a slice has a data structure called SliceHeader which is accessible through reflect package and is what being referred to when you use unsafe.Sizeof and taking address.

    The SliceHeader taking cares of three elements: Len,Cap and a Ptr. The fisrt two is trivail: they are what len() and cap() is for. The last one is a uintptr that points to the memory of the data the slice is containing.

    When you shallow-copy a slice, a new SliceHeader is created but with the same content, including Ptr. So the underlying memory is not copied, but shared.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 opencv图像处理,需要四个处理结果图
  • ¥20 centos linux 7.9安装php8.2.18不支持mysqli模块的问题
  • ¥15 stata空间计量LM检验
  • ¥15 NAO机器人说出txt文本内容
  • ¥15 关于k8s node节点被释放后如何驱逐节点并添加新节点
  • ¥15 subprocess.CalledProcessError: Command ‘[‘ninja‘, ‘-v‘]‘ returned non-zero exit status 1
  • ¥15 for循环处理大量数据怎么优化
  • ¥15 笔记本接显卡扩展坞重启报错
  • ¥15 为什么这个指令报错啊,一直弄不懂为什么,想问问该怎么弄,决求解决,ubuntu刚入手
  • ¥15 用百度飞将的paddleyolo库里的yolov7训练自己数据集