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 <[email protected]> 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 [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
