Anonymous user
Longest increasing subsequence: Difference between revisions
→Tcl: Added implementation
(→Tcl: Added implementation) |
|||
Line 74:
<pre>a L.I.S. of [3, 2, 6, 4, 5, 1] is [3, 4, 5]
a L.I.S. of [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] is [0, 4, 6, 9, 13, 15]</pre>
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<lang tcl>package require Tcl 8.6
proc longestIncreasingSubsequence {sequence} {
# Get the increasing subsequences (and their lengths)
set subseq [list 1 [lindex $sequence 0]]
foreach value $sequence {
set max {}
foreach {len item} $subseq {
if {[lindex $item end] < $value} {
if {[llength [lappend item $value]] > [llength $max]} {
set max $item
}
} elseif {![llength $max]} {
set max [list $value]
}
}
lappend subseq [llength $max] $max
}
# Pick the longest subsequence; -stride requires Tcl 8.6
return [lindex [lsort -stride 2 -index 0 $subseq] end]
}</lang>
Demonstrating:
<lang tcl>puts [longestIncreasingSubsequence {3 2 6 4 5 1}]
puts [longestIncreasingSubsequence {0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15}]</lang>
{{out}}
<pre>
3 4 5
0 4 6 9 13 15
</pre>
| |||