Heheh, three times slower but gives the wrong answer--maybe not a
great trade-off :o)
I'd misread the way the last if statements work in the Python
version. I modified mine to read:
(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))))
:else
(set (concat (when (>= (get-in c [i (dec j)])
(get-in c [(dec i) j]))
(backtrack-all c x y i (dec j)))
(when (>= (get-in c [(dec i) j])
(get-in c [i (dec j)]))
(backtrack-all c x y (dec i) j))))))
I'd mistakenly assumed that those last two conditionals were mutually
exclusive, but they're not.
Cheers,
Mark
On Jul 17, 7:07 pm, martin_clausen <[email protected]> wrote:
> 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 <[email protected]> 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 <[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
-~----------~----~----~----~------~----~------~--~---
