Thanks. Your code is definitely much more idiomatic Clojure - and 3X
faster. The lcs function does exactly what it is suppose to, but the
backtrack-all function only returns the first LCS found(for the
strings "AATCC" "ACACG" => ("ACC"), whereas the Python version returns
all the LCSes found (for the same strings => set(['ACC', 'AAC'])). I
have tried to find out why this is, but cannot identify the cause.
On Jul 17, 12:16 am, Mark Triggs <mark.h.tri...@gmail.com> wrote:
> Hi there,
>
> I had a bit of a go at converting the Python version into Clojure and
> removed the need to mutate an array. Because the 'lcs' function was
> basically just mapping over a list of i/j pairs and accumulating the
> resulting matrix, it seemed like a good candidate for reduce:
>
> (defn lcs [x y]
> (let [m (count x)
> n (count y)]
> (reduce (fn [c [i j]]
> (if (= (get x (dec i))
> (get y (dec j)))
> (assoc-in c [i j] (inc (get-in c [(dec i) (dec j)])))
> (assoc-in c [i j] (max (get-in c [i (dec j)])
> (get-in c [(dec i) j])))))
> (vec (replicate (inc n)
> (vec (replicate (inc m)
> 0))))
> (for [i (range 1 (inc m))
> j (range 1 (inc n))]
> [i j]))))
>
> Then, 'backtrack-all' is pretty much a straight translation of the
> Python one, but with tail recursion where possible:
>
> (defn backtrack-all [c x y i j]
> (cond (or (zero? i) (zero? j))
> #{""}
>
> (= (get x (dec i)) (get y (dec j)))
> (set (map #(str % (get x (dec i)))
> (backtrack-all c x y (dec i) (dec j))))
>
> (>= (get-in c [i (dec j)])
> (get-in c [(dec i) j]))
> (recur c x y i (dec j))
>
> (>= (get-in c [(dec i) j])
> (get-in c [i (dec j)]))
> (recur c x y (dec i) j)))
>
> Mostly untested ;o)
>
> Cheers,
>
> Mark
>
> On Jul 17, 6:57 am, martin_clausen <martin.clau...@gmail.com> wrote:
>
> > Can anybody give me some hints on how to translate this:http://bit.ly/lcs_py
> > (the backTrackAll function) from Python into Clojure? I have a pasted
> > my attempt here:http://paste.lisp.org/+1SL7, but it doesn't work. For
> > completeness I have included the functions required to test the
> > traceback-all-lcs function and my traceback-lcs function (that
> > works :-)).
>
> > I cannot figure out if it is the list comprehension that is wrong or
> > my use of cons or some immutability thing that is tricking me.
>
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
