算法-最小化布尔表达式

问题描述

我正在尝试编写一段代码，该代码可以将布尔表达式的LENGTH减小到最小，因此该代码应将表达式中的元素数量减少到最少.现在我被困住了，我需要一些帮助= [

I'm trying to write out a piece of code that can reduce the LENGTH of a boolean expression to the minimum, so the code should reduce the number of elements in the expression to as little as possible. Right now I'm stuck and I need some help =[

这是一条规则:布尔表达式中可以有任意数量的元素，但是它仅包含AND和OR运算符以及方括号.

Here's the rule: there can be arbitrary number of elements in a boolean expression, but it only contains AND and OR operators, plus brackets.

例如，如果我传入一个布尔表达式:ABC + BCD + DE，则最佳输出将是BC(A + D)+ DE，与原来的相比，这节省了2个单位空间，因为两个BC组合在一起了合而为一.

For example, if I pass in a boolean expression: ABC+BCD+DE, the optimum output would be BC(A+D)+DE, which saves 2 unit spaces compared to the original one because the two BCs are combined into one.

我的逻辑是，我将尝试在表达式中找到最常出现的元素，并将其分解出来.然后，我递归调用该函数，以对分解后的表达式执行相同的操作，直到完全分解为止.但是，如何在原始表达式中找到最常见的元素?也就是说，在上面的示例中，BC?似乎我必须尝试所有不同的元素组合，并找出每种组合出现在整个表达式中的次数.但这听起来真的很幼稚.第二

My logic is that I will attempt to find the most frequently appeared element in the expression, and factor it out. Then I call the function recursively to do the same thing to the factored expression until it's completely factored. However, how can I find the most common element in the original expression? That is, in the above example, BC? It seems like I would have to try out all different combinations of elements, and find number of times each combination appears in the whole expression. But this sounds really naive. Second

有人可以提示如何有效地做到这一点吗?甚至我可以在Google上搜索的某些关键字也可以.

Can someone give a hint on how to do this efficiently? Even some keywords I can search up on Google will do.

推荐答案

对不起，我还没有阅读所有这些很棒的算法，但是您询问了寻找共同因素的想法，所以我想到了以下几点:

Sorry I haven't read about all those cool algorithms yet, but you asked about finding the common factor, so I thought of the following:

import itertools
def commons(exprs):
    groups = []
    for n in range(2, len(exprs)+1):
        for comb in itertools.combinations(exprs, n):
            common = set.intersection(*map(set, comb))
            if common:
                groups.append(
                            (len(common), n, comb, ''.join(common)))
    return sorted(groups, reverse=True)

>>> exprs
['ABC', 'BCD', 'DE', 'ABCE']

>>> commons(exprs)
[(3, 2, ('ABC', 'ABCE'), 'ACB'),
 (2, 3, ('ABC', 'BCD', 'ABCE'), 'CB'),
 (2, 2, ('BCD', 'ABCE'), 'CB'),
 (2, 2, ('ABC', 'BCD'), 'CB'),
 (1, 2, ('DE', 'ABCE'), 'E'),
 (1, 2, ('BCD', 'DE'), 'D')]

该函数返回一个列表，按以下顺序排序:

The function returns a list sorted by:

1. 公因子的长度
2. 具有该公共因子的术语数

这篇关于算法-最小化布尔表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！