[FoRK] Data Structures Question
<andy at hexten.net> on
Tue Apr 3 03:50:44 PDT 2007
On 3 Apr 2007, at 05:33, Reza B'Far wrote:
> However, I purposefully am trying not to treat it as a "logic"
> question. I
> want to load n expressions into a structure, such as a tree, that
> has the
> properties that support the decomposition that I want.
> Essentially, what I
> want is to explode the boolean (Andy refers to this) but with some
> constraints... Get all the "anded" terms together in one single
> So, the subexpressions should only have AND's.
That /is/ a sum of products then... If you rewrite your original
expression in SoP form you get
(e1 && e2 && e5) || (e3 && e5) || (e4 && e5)
which is just your three AND terms ORed together.
> So, to summarize, I'm trying to find a structure that has this
> built in... which by several degrees of indirection means
> improved performance if you have n expressions and need to find the
> subexpressions and the path that was necessary to navigate to each
> randomly... basically, looking for the canonical solution... don't
> know if
> one exists or not.
I'm obviously having YASD but I'm still not really clear what you
mean. For your example does the tree look like this?
( or )
/ | \
/ | \
/ (and) \
/ / \ \
(and) e3 e5 (and)
/ | \ / \
e1 e2 e5 e4 e5
It might be worth looking at this:
Unfortunately it's binary-only but, if nothing else, some of the
links might be useful. I recently used it in conjunction with a
little Perl wrapper to semi-automatically refactor a bunch of complex
 Yet Another Stupid Day
Andy Armstrong, hexten.net
More information about the FoRK