I got an idea which probably doesn't perform very well although I found it a little interesting. https://gist.github.com/999430
It simply groups the strings together, saying: * if the first and second characters are the same, they only differ in one position. * if the second and last characters ... * if the first and last characters ... Jonathan On Mon, May 30, 2011 at 10:41 PM, Ken Wesson <kwess...@gmail.com> wrote: > There's no really easy way to avoid O(n^2) comparison when you want to > check everything against everything else in some set. One efficiency > that halves the size of the job (but does not reduce big-O) is to > check only against the later items: > > (defn pairs-off-one [strs] > (let [istrs (map-indexed vector strs)] > (for [[n1 s1] istrs > [n2 s2] istrs > :when (and > (< n1 n2) > (= (reduce + (map #(if (= %1 %2) 0 1) s1 s2)) 1))] > [s1 s2]))) > > => (pairs-off-one ["abc" "abd" "aed" "axf" "zqr" "zbc" "aqd"]) > (["abc" "abd"] ["abc" "zbc"] ["abd" "aed"] ["abd" "aqd"] ["aed" "aqd"]) > > I don't think you'll get much better than that even with things like > radix or finger trees. If you were looking for strings with a long > common prefix radix trees would help enormously, but the differences > can be anywhere in your strings. On the brighter side, if the strings > are of length 3 and usually confined to printable US-ASCII characters > you have only about 96^6 comparisons to do in the absolute worst case. > :) > > -- > 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 > -- 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
