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?

Answer 1

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.