Updated 2014-06-07 20:21:09 by pooryorick

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]