Hello friends,
I am writing a program to generate directions for humans to read. The
directions are composed of a collection with a series of steps, some
of which may be duplicated:
[:a :b :c :a :b :c]
I would like to compress them by indicating repeats, using this
notation:
[[2 [:a :b :c]]
Since the directions will be read by humans (after some formatting), I
am limiting nesting to one level. So the following would be an invalid
transformation:
[:a :b :a :b :c :a :b :a :b :c] => [[2 [2 [:a :b]] :c]]
My current algorithm for the compress has O(2^n) complexity, which
makes it useless except for the most trivial cases. I'm looking for
something that runs in polynomial time or better. To give some
context, my current algorithm is as follows:
1. Generate the set indices for the power set of the directions (e.g.
(powerset [:a :b :c]) => [[] [1 0 0] [1 1 0] ...]).
2. For each index, use partition-by to generate a set of groups of the
vector (e.g. [1 1 0] => [[:a :b] [:c]]). Since [1 1 0] and [0 0 1] are
identical for my needs, take the distinct groupings (only generating
the distinct groups would only be O(2^{n-1]), so I haven't bothered to
shave computations here).
3. For each grouping, merge identical groups from left to right.
4. Score all the groupings by counting the number of steps (symbols in
these examples). The grouping with the fewest steps is the "best".
I've looked at some string searching algorithms (Boyer-Moore, e.g.),
but these seem geared towards finding a specific substring in a larger
string. Perhaps these algorithms would apply to my problem, but I'm
just not seeing it.
Thanks in advance for your help. All suggestions are welcome.
-Mark
--
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
