Anonymous user
Longest increasing subsequence: Difference between revisions
added go
(→Patience sorting: make it one function) |
(added go) |
||
Line 236:
<pre>[ 2 4 5 ]
[ 0 2 6 9 11 15 ]</pre>
=={{header|Go}}==
Patience sorting
<lang go>package main
import (
"fmt"
"sort"
)
type Node struct {
val int
back *Node
}
func lis (n []int) (result []int) {
var pileTops []*Node
// sort into piles
for _, x := range n {
j := sort.Search(len(pileTops), func (i int) bool { return pileTops[i].val >= x })
node := &Node{ x, nil }
if j != 0 { node.back = pileTops[j-1] }
if j != len(pileTops) {
pileTops[j] = node
} else {
pileTops = append(pileTops, node)
}
}
if len(pileTops) == 0 { return []int{} }
for node := pileTops[len(pileTops)-1]; node != nil; node = node.back {
result = append(result, node.val)
}
for i := 0; i < len(result)/2; i++ {
result[i], result[len(result)-i-1] = result[len(result)-i-1], result[i]
}
return
}
func main() {
for _, d := range [][]int{{3, 2, 6, 4, 5, 1},
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}} {
fmt.Printf("an L.I.S. of %v is %v\n", d, lis(d))
}
}</lang>
{{out}}
<pre>an L.I.S. of [3 2 6 4 5 1] is [2 4 5]
an L.I.S. of [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15] is [0 2 6 9 11 15]</pre>
=={{header|Haskell}}==
Line 421 ⟶ 470:
my @d = @$r;
my @lis = lis(@d);
print "an L.I.S. of [@d] is [@lis]\n";
}</lang>
{{out}}
<pre>an L.I.S. of [3 2 6 4 5 1] is [2 4 5]
an L.I.S. of [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15] is [0 2 6 9 11 15]</pre>
=={{header|Perl 6}}==
| |||