Walking a boolean tree to produce matching inputs

[japhy]

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?

[AnomalousMonk]

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.

[LanX]

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! :)

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.

[BrowserUk]

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

[japhy]

It does not need representation.

[kennethk]

What about ordering? Does "light green" pass?

[japhy]

Yes, "light green" passes. Order does not matter.

[japhy]

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}"...

[hdb]

Have a look at this recent thread: Optimize a generic boolean expression.

[Anonymous Monk]

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

[japhy]

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;
    }
  }
}