jbr 2013-02-09: Here is a little thing from
Patience sort and the Longest increasing subsequence
, Thomas Guest, 2009-03-26.
Remember that Tcl is a poor fit for data structures!
PYK 2014-06-07, assumes that remark is saracastic, since the
Python implementation on that page is no cleaner.
source iter.tcl ; # you'll need this http://wiki.tcl.tk/37704
set data {
x
11 3 4 8 2 12 9 13 5 7 6 10 14
}
set n [lindex $data 0]
set seq [lrange $data 1 end]
iterator psort seq {
set tops {}
foreach x $seq {
set pile [expr {[lsearch -real -bisect $tops $x] + 1}]
lset tops $pile $x
yield [list $x $pile]
}
}
proc lis seq {
iterate {x pile} {psort $seq} {
if {$pile > 0} {
set prev [expr {[llength [dict get $piles [expr $pile-1]]]-1}]
} else {
set prev {}
}
dict lappend piles $pile [list $prev $x]
}
set prev 0
foreach pile [lreverse [dict keys $piles]] {
lappend lis [lassign [lindex [dict get $piles $pile] $prev] prev]
}
lreverse $lis
}
puts [lis $seq]
