5

I'm trying to learn Go but I can't figure it out why this code at the end of the recursion call stack returns an empty slice, any help? Also tmp doesn't even seem to register in the debugger.

func main() {
    input := [3]int{4, 6, 7}
    // expected [[6,7],[4,6,7],[4,6],[4,7]]
    fmt.Println(findSubsequences(input))
}

func findSubsequences(nums [3]int) [][]int {
    res := [][]int{}
    list := []int{}
    findSubsequence(res, list, nums, 0)
    return res
}

func findSubsequence(res [][]int, list []int, nums [3]int, id int) [][]int {
    if len(list) > 1 {
        tmp := make([]int, len(list))
        copy(tmp, list)
        res = append(res, tmp)
    }
    var unique []int
    for i := id; i < len(nums); i++ {
        if id > 0 && nums[i] < nums[id-1] {
            continue // skip non-increase
        }
        if contains(unique, nums[i]) {
            continue // skip duplicate
        }
        unique = append(unique, nums[i])
        list = append(list, nums[i])
        findSubsequence(res, list, nums, id+1)
        list = list[:len(list)-1]
    }
    return res
}

func contains(s []int, e int) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}
John
  • 61
  • 1
  • 3
  • 3
    You must assign the return value of `findSubsequence()` to `res`, e.g. `res = findSubsequence(res, list, nums, 0)`, and when called recursively: `res = findSubsequence(res, list, nums, id+1)`. This alone won't make the algorithm correct, but you'll start seeing results. – icza Aug 25 '17 at 11:04
  • thank you, but can you please give me an idea why is happening? in Java you should pass an ArrayList and you're fine. – John Aug 25 '17 at 11:26
  • 2
    Java uses pass-by-reference. Go uses pass-by-copy (or pass-by-value). See [Are golang slices pass by value?](https://stackoverflow.com/questions/39993688/are-golang-slices-pass-by-value/39993797#39993797); and [Are Golang function parameter passed as copy-on-write?](https://stackoverflow.com/questions/33995634/are-golang-function-parameter-passed-as-copy-on-write/33995762#33995762) – icza Aug 25 '17 at 11:37
  • @icza I did sort of knew this, but `all slices which share the same backing array will "observe" the change.` according to this should not work as a java pass-by-reference? – John Aug 25 '17 at 11:44
  • 1
    As long as you only modify _elements_ of the slice, but not the slice header itself. Appending to a slice *does* modify the slice header (you assign the result to the variable holding the slice header e.g. `unique = append(unique, nums[i])`), so your statement no longer applies. – icza Aug 25 '17 at 12:01
  • 1
    @John `append` will only write to the same backing array if it's big enough. If it isn't, the array will be copied and the slice returned will have a new backing array. – Art Aug 25 '17 at 12:01
  • @Art I suspected that may be the case, but I tried with a verry large initial `res` and didn't worked, I guess append modifies the header, no matter what. – John Aug 25 '17 at 12:05
  • 1
    @John Append does not modify the header (it can't, as it receives only a copy of it), it _returns_ the new header, and the _assignment_ of the return value is what "modifies" the header. – icza Aug 25 '17 at 12:21

2 Answers2

6

This is the solution to get your code to append the slice. In GO, if you are recursively passing a slice, you must pass it by reference. So this solves the problem that you are experiencing where your code will return empty slice. But your algorithm seems incorrect for the result that you are expecting.

func main() {
    input := [3]int{4, 6, 7}
    // expected [[6,7],[4,6,7],[4,6],[4,7]]
    fmt.Println(findSubsequences(input))
}

func findSubsequences(nums [3]int) [][]int {
    res := [][]int{}
    list := []int{}
    fmt.Print(nums)
    findSubsequence(&res, list, nums, 0)
    return res
}

func findSubsequence(res *[][]int, list []int, nums [3]int, id int) [][]int {
    var tmp []int
    if len(list) > 1 {
        tmp = make([]int, len(list))
        copy(tmp, list)
    fmt.Println(tmp)
        *res = append(*res, tmp)
    }
    var unique []int
    for i := id; i < len(nums); i++ {
        if id > 0 && nums[i] < nums[id-1] {
            continue // skip non-increase
        }
        if contains(unique, nums[i]) {
            continue // skip duplicate
        }
        unique = append(unique, nums[i])
        list = append(list, nums[i])
        findSubsequence(res, list, nums, id+1)
    list = list[:len(list)-1]

    }
    return *res
}

func contains(s []int, e int) bool {
    for _, a := range s {
        if a == e || a >e {
            return true
        }
    }
    return false
}
bashxx
  • 111
  • 3
  • right, the algorithm might be incorrect, didn't got to look into it due to not being to append recursively, but `findSubsequence(res, list, nums, id+1)` the recursively call should not be `findSubsequence(&res, list, nums, id+1)` ? Or maybe not, since res is a pointer at that point, but I'm still a bit confused as to why it happens, I know about go pointers, but a slice is a reference to a backing array, so is a pointer itself, I guess append, recreates the backing array no matter what, since it didn't worked with a pre-allocated huge res slice. – John Aug 27 '17 at 07:13
-2

I used global variables in the end, but is still not OK, it works slower than Java, anyway here is the code.

var res = [][]int{}
var list = []int{}

func findSubsequences(nums [3]int) [][]int {
    findSubsequence(nums, 0)
    return res
}

func findSubsequence(nums [3]int, id int) {
    if len(list) > 1 {
        tmp := make([]int, len(list))
        copy(tmp, list)
        res = append(res, tmp)
    }
    var unique []int
    for i := id; i < len(nums); i++ {
        if id > 0 && nums[i] < nums[id-1] {
            continue // skip non-increase
        }
        if contains(unique, nums[i]) {
            continue // skip duplicate
        }
        unique = append(unique, nums[i])
        list = append(list, nums[i])
        findSubsequence(nums, i+1)
        list = list[:len(list)-1]
    }
}

func contains(s []int, e int) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}
John
  • 61
  • 1
  • 3