How to efficiently distribute a logical expression in javascript

Question

Suppose you have this logical expression

(A or B or C) and (D or E) and (F or G or H)

As you see here, we have OR operator inside the parentheses and AND operator in the outside. We can say that this logical expression is of type AND(OR).

I want to convert this expression to OR(AND).

Example:

(A or B) and (C or D) = (A and C) or (A and D) or (B and C) or (B and D)

A simple way to implement this (in javascript):

class OrNode<C = string> {
    /* constructor logic */
    nodeType = 'OR';
    children: C[];
}

class AndNode<C = string> {
    /* constructor logic */
    nodeType = 'AND';
    children: C[];
}

function convert(expression: AndNode<OrNode>): OrNode<AndNode> {
    let children: AndNode[] = [{ nodeType: 'AND', children: [] }];
    expression.children.forEach((orNode) => {
        let temp = children;
        children = [];
        orNode.children.forEach((leafNode) => {
            temp.forEach((andNode) => {
                children.push({
                    nodeType: 'AND',
                    children: [...andNode.children, leafNode],
                });
            });
        });
    });
    return new OrNode<AndNode>({ nodeType: 'OR', children });
}

Suppose we have this expression:

const expression = new AndNode<OrNode>({
    nodeType: 'AND',
    children: [
        { nodeType: 'OR', children: ['A', 'B', 'C'] },
        { nodeType: 'OR', children: ['D', 'E'] },
        { nodeType: 'OR', children: ['F', 'G', 'H'] },
    ]
});

Then if we do the convert, the new converted expression will be equal to

{
    nodeType: 'OR',
    children: [
        { nodeType: 'AND', children: ['A', 'D', 'F'] },
        { nodeType: 'AND', children: ['A', 'D', 'G'] },
        { nodeType: 'AND', children: ['A', 'D', 'H'] },
        { nodeType: 'AND', children: ['A', 'E', 'F'] },
        { nodeType: 'AND', children: ['A', 'E', 'G'] },
        { nodeType: 'AND', children: ['A', 'E', 'H'] },
    
        { nodeType: 'AND', children: ['B', 'D', 'F'] },
        { nodeType: 'AND', children: ['B', 'D', 'G'] },
        { nodeType: 'AND', children: ['B', 'D', 'H'] },
        { nodeType: 'AND', children: ['B', 'E', 'F'] },
        { nodeType: 'AND', children: ['B', 'E', 'G'] },
        { nodeType: 'AND', children: ['B', 'E', 'H'] },

        { nodeType: 'AND', children: ['C', 'D', 'F'] },
        { nodeType: 'AND', children: ['C', 'D', 'G'] },
        { nodeType: 'AND', children: ['C', 'D', 'H'] },
        { nodeType: 'AND', children: ['C', 'E', 'F'] },
        { nodeType: 'AND', children: ['C', 'E', 'G'] },
        { nodeType: 'AND', children: ['C', 'E', 'H'] },
    ]
}

The complexity of this brute force solution is O(M^N), M is the highest number of conditions between parentheses, and N is the number of the parentheses blocks.

Is there a way to have another algorithm and reduce this complexity?

You mean my brute force algorithm ? yes, but the code I posted is just to show the idea of the convert algorithm. The actual code contains more details (guards, the constructor logic, etc). This brute force algorithm is causing our servers to restart frequently when working with big logical expressions. — MChaker, Feb 21 '23 at 12:07
you could take a [generator](https://stackoverflow.com/a/44012184/1447675) for creating the cartesian product. maybe this helps a bit. — Nina Scholz, Feb 21 '23 at 12:13
Reminds me of `(a && b) == !(!a || !b)`. Possibly a not operation in conversion could be useful. — traktor, Feb 21 '23 at 12:39
@traktor unfortunately using a not operation is not possible. — MChaker, Feb 21 '23 at 12:47

score 5 · Answer 1 · answered Feb 21 '23 at 13:43

You have an expression in "conjunctive normal form", and you want to convert it to "disjunctive normal form".

A conversion is always possible, but it also solves NP-hard problems like boolean satisfiability, and so there is no known efficient way to even determine if the resulting formula will be empty or not.

In fact, for some inputs, the resulting formula will be exponential in size, so efficient conversion is certainly impossible. A simple example of this is given in the DNF wikipedia article above:

(a₁ or b₁) and (a₂ or b₂) and ... (a_n or b_n)

Will expand in DNF to contain 2ⁿ terms.

Scott Sauyet · Answer 2 · 2023-07-05T13:34:10.160

As others have already pointed out, the complexity is inherent in the problem. If you have n1 children in the first node, n2 in the second, and so on for k nodes, then the final answer will have n1 * n2 * ... * nk results.

But you can build the implementation atop a simple cartesian product generator, like this:

const cartesian = ([xs, ...xss]) =>
  xs == undefined ? [[]] : xs .flatMap (x => cartesian (xss) .map (ys => [x, ...ys]))

const andOr2orAnd = ({children = []}) => ({
  nodeType: 'OR',
  children: cartesian (children .map (n => n .children)) 
              .map (cs => ({nodeType: 'AND', children: cs}))
})

const expression = {nodeType: 'AND', children: [{nodeType: 'OR', children: ['A', 'B', 'C']}, {nodeType: 'OR', children: ['D', 'E']}, {nodeType: 'OR', children: ['F', 'G', 'H']}]}

console .log (andOr2orAnd (expression))

.as-console-wrapper {max-height: 100% !important; top: 0}

cartesian works like this:

cartesian ([['a', 'b'], [1, 2, 3], [true, false]]) //=> [
// ["a", 1, true], ["a", 1, false], ["a", 2, true], ["a", 2, false], 
// ["a", 3, true], ["a", 3, false], ["b", 1, true], ["b", 1, false], 
// ["b", 2, true], ["b", 2, false], ["b", 3, true], ["b", 3, false]
//]

I find this code simpler.

Update

This is a much more efficient version of cartesian:

const cartesian = ([xs, ...xss]) => ((kids) =>
  xs == undefined ? [[]] : xs .flatMap (x => kids .map (ys => [x, ...ys]))
)(xs && cartesian(xss))

(The one above was recreating the equivalent of kids for every value in xs.)

How to efficiently distribute a logical expression in javascript

2 Answers2

Update