Weird error trying to generate increasing sequences in Go

Viewed 47

Trying to use dynamic programming to generate all possible length-k subsequences of 0..n-1 inclusive in Go. Running into an issue where I get duplicate sequences. With small n,k it seems to be fine but when I try n=43,k=5 I get the error.

Code:

func genSequences(n int, k int) [][]int {
    H := [][][][]int{}
    for i := 0; i < n; i++ {
        H = append(H,[][][]int{})
        for j := 0; j < n; j++ {
            H[i] = append(H[i],[][]int{})
        }
    }

    H[0][0] = [][]int{[]int{0}}
    for i := 1; i < n; i++ {
        H[i][0] = append(H[i-1][0],[]int{i})
    }
    for j := 1; j < k; j++ {
        H[j][j] = [][]int{append(H[j-1][j-1][0], j)}
    }

    for j := 1; j < k; j++ {
        for i := j+1; i < n; i++ {
            curr := append([][]int{}, H[i-1][j-1]...)
            for y := 0; y < len(curr); y++ {
                curr[y] = append(curr[y],i)
            }
            H[i][j] = append(H[i-1][j],curr...)
        }
    }

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

Test

func strRep(lst []int) string {
    result := ""
    for i := 0; i < len(lst) - 1; i++ {
        result = result + strconv.FormatInt(int64(lst[i]), 10)
        result = result + ","
    }
    result = result + strconv.FormatInt(int64(lst[len(lst)-1]),10)
    return result
}

func main() {
    sequences := genSequences(43, 5)
    thing := true
    gah := make(map[string] int)
    for s := 0; s < len(sequences); s++ {
        if gah[strRep(sequences[s])] > 0 {
            thing = false
        }
        gah[strRep(sequences[s])] = 1
    }
    fmt.Println(thing)
}

The test outputs false to the console for the aforementioned example n=43,k=5. For smaller inputs it outputs true.

0 Answers
Related