[Cs254f11] Recursion without loop

[Thomas Helmuth]

After thinking about it some more, I think the following solution fixes my
efficiency problem while simplifying the function. I'm not guaranteeing it
works, but I think it will.

(defn lib-test
  [x y checked]
  (if (some #{[x y]} checked)
    checked
    (reduce #(lib-test (first %2)
                       (second %2)
                       (clojure.set/union %1 #{[x y]}))
            (cons checked (friends x y)))))

The main power here is done with 'reduce', which in this case takes a list
composed of 'checked' followed by a bunch of x-y pairs. This way, it should
run in linear time instead of n^2.

-Tom

On Wed, Nov 2, 2011 at 9:54 PM, Thomas Helmuth <thGST at hampshire.edu> wrote:

> I would be tempted to write a more recursive, slightly simpler solution to
> this problem. I have no idea if the following solution is more or less
> efficient than Lee's code, and also have not tested it.
>
>
> (defn lib-test
>   [x y checked]
>   (if (some #{[x y]} checked)
>     checked
>     (apply clojure.set/union
>            (map #(lib-test (first %)
>                            (second %)
>                            (clojure.set/union checked #{[x y]}))
>                 (friends x y)))))
>
> This code is called on an x-y pair and an empty set, and returns a set of
> pairs. If the pair is in 'checked', then it just returns 'checked'.
> Otherwise, it maps a function over the sequence returned by 'friends'. The
> mapping function takes an x-y pair from 'friends' and recursively calls
> lib-test on the pair as well as 'checked' with [x y] added. The map results
> in a sequence of sets, where each set contains pairs that are in the group.
> Thus, we can just union them together to get the result.
>
> Now that I think about it, this might find every path to every stone in a
> group. This may be of some concern, since it makes an algorithm that runs
> in O(n^2) time for a problem that should be solvable in linear time. Maybe
> to improve the efficiency, you need to do something like what Lee did. But,
> it's always helpful to see a different solution.
>
> -Tom
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.hampshire.edu/pipermail/cs254f11/attachments/20111102/ceaaf4cb/attachment.htm>