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.