Anonymous user
Longest increasing subsequence: Difference between revisions
added Clojure version
(sequences) |
(added Clojure version) |
||
Line 11:
# An efficient solution can be based on [[wp:Patience sorting|Patience sorting]].
=={{header|Clojure}}==
Implementation using the Patience Sort approach. The elements (''newelem'') put on a pile combine the "card" with a reference to the top of the previous stack, as per the algorithm. The combination is done using ''cons'', so what gets put on a pile is a list -- a descending subsequence.
<lang Clojure>(defn place [piles card]
(let [[les gts] (->> piles split-with #(<= (ffirst %) card))
newelem (cons card (->> les last first))
modpile (cons newelem (first gts))]
(concat les (cons modpile (rest gts)))))
(defn a-longest [cards]
(let [piles (reduce place '() cards)]
(->> piles last first reverse)))
(println (a-longest [3 2 6 4 5 1]))
(println (a-longest [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15]))</lang>
Output:
<lang>(2 4 5)
(0 2 6 9 11 15)</lang>
=={{header|Common Lisp}}==
===Common Lisp: Using the method in the video===
| |||