http://www.perlmonks.org?node_id=1079118

japhy has asked for the wisdom of the Perl Monks concerning the following question:

I've got a series of boolean logic statements, such as "(green OR yellow) AND (light OR banana)" or "peace AND justice AND liberty AND NOT (corrupt OR evil)".

I have a parser which builds trees out of these statements: [AND, [OR, green, yellow], [OR, light, banana]] for the first, and [AND, peace, justice, liberty, [NOT, [OR, corrupt, evil]]] for the second.

I would now like to walk these trees to build a list of the minimal inputs which will pass the boolean logic. So for the first, I'd like to build the list ("green light", "green banana", "yellow light", "yellow banana"), and for the second I'd like to build the list ("peace justice liberty"). (There is no need to generate the various permutations of the terms "peace", "justice", and "liberty".)

I know this will be a recursive process, and I know an "OR" branch with X children will require locally producing X copies of the list, but I'm having trouble figuring out how to start. It's super easy with something like "a OR b OR c", or "a AND b AND c", but when the recursion comes into play, that's where my programmer's block kicks in.

Can anyone offer some pointers to move me in the right direction?

Jeffrey Pinyan (Perl, PHP ugh, JavaScript) — @PrayingTheMass
Melius servire volo
Catholic Liturgy

Replies are listed 'Best First'.
Re: Walking a boolean tree to produce matching inputs
by AnomalousMonk (Bishop) on Mar 20, 2014 at 17:54 UTC

    Maybe see section 4.3.2 Genomic Sequence Generator of Dominus's Higher Order Perl (free download here) for something (at least remotely) like this.

Re: Walking a boolean tree to produce matching inputs
by LanX (Cardinal) on Mar 20, 2014 at 18:56 UTC
    I would go top down.

    The minimal solutions of:

    • ... an AND expression are the smallest combinations of minimal solutions of subexpressions.
    • ... an OR expression are the smallest of the minimal solutions of subexpressions.
    • .... an ATOM is the ATOM
    so
    •  A = min ([OR, green, yellow]) = min (min( "green") + min("yello") ) = min { {green}, {yellow} }
    •  B = min ([OR, light, banana]) = min (min( "light") + min("banana")) = min { {light}, {banana} }
    •  C = min( [AND, A, B]) = min ( A x B ) = min { {green}, {yellow} } x { {light}, {banana} }

    It gets complicated if ATOMs are repeated, so you'll have to compute all possible solutions to find the minimas.

    e.g. min ( ( a or b ) and ( a or c ) ) = { {a} } cause {a} x {a} = {a} and the other solutions like {b,a}, etc are bigger

    HTH! :)

    Cheers Rolf

    ( addicted to the Perl Programming Language)

    updates

  • please note that this is related to transforming and minimizing terms. This rings a bell ... we used something like the Horner scheme to solve such tasks at my first year in university... :)

  • you can also approach this with logical operations on bit-vectors representing the truth tables, but be aware that already 10 atoms would require 1024 bit strings to do so.
Re: Walking a boolean tree to produce matching inputs
by BrowserUk (Pope) on Mar 20, 2014 at 17:46 UTC

    How would you represent the "and not" part of your second example as a "minimal input"?


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Walking a boolean tree to produce matching inputs
by kennethk (Abbot) on Mar 20, 2014 at 18:05 UTC

    What about ordering? Does "light green" pass?


    #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

Re: Walking a boolean tree to produce matching inputs
by japhy (Canon) on Mar 20, 2014 at 18:01 UTC

    Just realized I could cheat and have glob() do the hard work for me, by converting the boolean trees into glob-style statements, e.g. "{green,yellow}~{light,banana}"...

    Jeffrey Pinyan (Perl, PHP ugh, JavaScript) — @PrayingTheMass
    Melius servire volo
    Catholic Liturgy
Re: Walking a boolean tree to produce matching inputs
by hdb (Monsignor) on Mar 21, 2014 at 14:07 UTC
Re: Walking a boolean tree to produce matching inputs
by Anonymous Monk on Mar 21, 2014 at 07:47 UTC

    Might be easier to pawn off to one of these :)
    String::Glob::Permute - Expand {foo,bar,baz}[2-4] style string globs
    Text::Glob::Expand - permute and expand glob-like text patterns
    update: not much luck with this one :) Regexp::Genex - get the strings a regex will match, with a regex

Re: Walking a boolean tree to produce matching inputs
by japhy (Canon) on Sep 18, 2014 at 02:29 UTC

    I have finally solved this problem, after months of cheating and using File::Glob to do the hard work for me. (I ran into string-length limitations with File::Glob which prevented it from working for very long boolean statements.)

    Here is my Perl solution, translated from (obligatory shudder) PHP. Hopefully the code speaks for itself and is not in need of much documentation for explaining its logic. NOTE: "not" nodes are skipped, because the point of this function is to come up with lists of terms that will match the logic.

    #!/usr/bin/perl -l use strict; use warnings; my $tree = ['and', ['or', 1, 2], ['not', 3], ['or', 4, 5, 6]]; my $opts = options($tree); for my $o (@$opts) { print "OPTION: ", join(", ", @$o); } sub options { my ($tree, $opts) = @_; if (! $opts) { $opts = [ [] ]; options($tree, $opts); return $opts; } else { my $op = $tree->[0]; if ($op eq 'and') { for my $val (@$tree[1 .. $#$tree]) { if (ref($val) eq 'ARRAY' and ($val->[0] eq 'and' or $val->[0] +eq 'or' or $val->[0] eq 'not')) { my $subtree = options($val); my @new; for my $branch (@$subtree) { for my $o (@$opts) { push @new, [ @$o, @$branch ]; } } @$opts = @new; } else { for my $o (@$opts) { push @$o, $val; } } } } elsif ($op eq 'or') { my @new; for my $val (@$tree[1 .. $#$tree]) { if (ref($val) eq 'ARRAY' and ($val->[0] eq 'and' or $val->[0] +eq 'or' or $val->[0] eq 'not')) { my $subtree = options($val); for my $branch (@$subtree) { for my $o (@$opts) { push @new, [@$o, @$branch]; } } } else { for my $o (@$opts) { push @new, [@$o, $val]; } } } @$opts = @new; } } }
    Jeffrey Pinyan (Perl, PHP ugh, JavaScript) — @PrayingTheMass
    Melius servire volo
    Catholic Liturgy