jbr 2013-02-09 - Here is a little thing from here: http://wordaligned.org/articles/patience-sort
Remember that tcl is a poor fit for data structures!
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 [lreverse $seq] {
set pile [expr [lsearch -real -bisect $tops $x] + 1]
if { $pile < [llength $tops] } {
lset tops $pile $x
} else {
lappend tops $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]