40 lines
960 B
Go
40 lines
960 B
Go
package main
|
|
|
|
import "fmt"
|
|
|
|
const ( // state:
|
|
m = iota // missing: all elements missing so far
|
|
c // continuous: all elements included so far are continuous
|
|
cm // one or more continuous followed by one or more missing
|
|
cmc // non-continuous subsequence
|
|
)
|
|
|
|
func ncs(s []int) [][]int {
|
|
if len(s) < 3 {
|
|
return nil
|
|
}
|
|
return append(n2(nil, s[1:], m), n2([]int{s[0]}, s[1:], c)...)
|
|
}
|
|
|
|
var skip = []int{m, cm, cm, cmc}
|
|
var incl = []int{c, c, cmc, cmc}
|
|
|
|
func n2(ss, tail []int, seq int) [][]int {
|
|
if len(tail) == 0 {
|
|
if seq != cmc {
|
|
return nil
|
|
}
|
|
return [][]int{ss}
|
|
}
|
|
return append(n2(append([]int{}, ss...), tail[1:], skip[seq]),
|
|
n2(append(ss, tail[0]), tail[1:], incl[seq])...)
|
|
}
|
|
|
|
func main() {
|
|
ss := ncs([]int{1, 2, 3, 4})
|
|
fmt.Println(len(ss), "non-continuous subsequences:")
|
|
for _, s := range ss {
|
|
fmt.Println(" ", s)
|
|
}
|
|
}
|