4

我需要帮助从表达式中提取所有最小真实条件（如 sql 中的 where 子句）

假设我有这样的表达：

例如1：

((A & B ) & (C | D))
output should be:
((A & B) | C)
((A & B) | D)

例如 2：

((A | B) & (C | D))
output should be:
(A & C)
(A & D)
(B & C)
(B & D)

例如 3：

(A | B | C)
output should be :

(A)
(B)
(C)

注意：'|' represent 'OR'and '&' represent 'AND'，所以想把一个大条件分解成所有可能的最小真实条件。

请建议...

4

3 回答 3

3

因此，似乎有一种方法可以帮助您将表达式简化为乘积之和。通过将它以产品总和形式呈现，您将拥有一系列不同的选项，如果其中包含的所有值都为真，则每个选项都是唯一正确的选项。

处理此问题的一种方法是使用复合模式。我们将从我们的IExpression界面开始：

public interface IExpression<T>
{
    int NumberOfPossibilities();

    IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities();
    IEnumerable<ValueExpression<T>> GetNthPossibility(int n);
}

这里的重点是第一种和最后一种方法。我们需要能够知道给定表达式有多少种可能性，以及获得第 N 种可能性的简单方法。最后一种方法的约定是所有给定的值都需要为第 N 种可能性为真。对于第二种方法，外部可枚举是所有表达式一起被 ORed，而每个内部表达式需要被 ANDed 一起。

将有三种实现方式。AValueExpression只表示一个值，anAndExpression表示将 N 个表达式组合在一起，而 anOrExpression表示将 N 个表达式组合在一起。

Value 是最容易实现的：

public class ValueExpression<T> : IExpression<T>
{
    public T Value { get; set; }
    public ValueExpression(T value)
    {
        Value = value;
    }

    public int NumberOfPossibilities()
    {
        return 1;
    }

    public IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities()
    {
        return new[] { new[] { this } };
    }

    public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
    {
        return new[] { this };
    }
}

And 表达式更复杂一些。AND 表达式的可能性数是被 AND 的可能性数的乘积。

要获得第 N 种可能性，您可以这样认为：

从0开始；对于 0，结果需要将每个子表达式的第一种可能性 AND 一起。对于第一种可能性，我们将一个添加到第一个子表达式。每次 n 上升时，我们都会增加从第一个子表达式中获得的排列。当我们通过它的计数时，它会回到零，并且下一个子表达式增加一。它基本上就像计数，但每个数字代表一个子表达式，而该数字的基数是该子表达式的可能性计数。

public class AndExpression<T> : IExpression<T>
{
    private IList<IExpression<T>> expressions;
    public AndExpression(IList<IExpression<T>> expressions)
    {
        this.expressions = expressions;
    }

    public int NumberOfPossibilities()
    {
        return expressions.Aggregate(1,
            (acc, expression) => acc * expression.NumberOfPossibilities());
    }

    IEnumerable<IEnumerable<ValueExpression<T>>> IExpression<T>.Possibilities()
    {
        return Enumerable.Range(0, NumberOfPossibilities())
            .Select(n => GetNthPossibility(n));
    }

    public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
    {
        for (int i = 0; i < expressions.Count; i++)
        {
            int count = expressions[i].NumberOfPossibilities();
            foreach (var value in expressions[i].GetNthPossibility(n % count))
                yield return value;

            n /= count;
        }
    }
}

对于 OR 表达式，它与 AND 版本相似，但仍然不同。

可能性的数量是总和，而不是内部表达式计数的乘积。

为了获得第 n 种可能性，我们仅从其中一个子表达式的一种可能性中返回项目，而不是像 AND 那样从每个可能性中返回一个。

public class OrExpression<T> : IExpression<T>
{
    private IList<IExpression<T>> expressions;
    public OrExpression(IList<IExpression<T>> expressions)
    {
        this.expressions = expressions;
    }

    public int NumberOfPossibilities()
    {
        return expressions.Sum(expression => expression.NumberOfPossibilities());
    }

    public IEnumerable<IEnumerable<ValueExpression<T>>> Possibilities()
    {
        return Enumerable.Range(0, NumberOfPossibilities())
            .Select(n => GetNthPossibility(n));
    }

    public IEnumerable<ValueExpression<T>> GetNthPossibility(int n)
    {
        for (int i = 0; i < expressions.Count; i++)
        {
            int count = expressions[i].NumberOfPossibilities();
            if (n < count)
                return expressions[i].GetNthPossibility(n);
            else
                n -= count;
        }

        throw new ArgumentOutOfRangeException();
    }
}

这是一个将表达式打印为字符串的简单函数：

public static void PrintPossibilities<T>(IExpression<T> expression)
{
    Console.WriteLine(string.Join(" + ", expression.Possibilities()
            .Select(possibility =>
                string.Concat(possibility.Select(value => value.Value)))));
}

请注意，这不处理解析表达式，只是在解析后处理它。

这是您的第一个示例的测试：

var AB = new AndExpression<string>(new[]{
    new ValueExpression<string>("A"),
    new ValueExpression<string>("B")});

var CD = new OrExpression<string>(new[]{
    new ValueExpression<string>("C"),
    new ValueExpression<string>("D")});

var exp = new AndExpression<string>(new IExpression<string>[] { AB, CD });

PrintPossibilities(exp);

哪个打印：

ABC + ABD

AB 更改为 OR 表达式（您的第二个示例）打印：

AC + BC + AD + BD

您的第三个选项可以表示为：

var third = new OrExpression<string>(new[]{
    new ValueExpression<string>("A"),
    new ValueExpression<string>("B"),
    new ValueExpression<string>("C")});

打印时会导致：

A + B + C

于 2013-07-01T18:40:18.297 回答
1

我知道您要的是一组表达式，每个表达式都暗示输入。也就是说，如果这些表达式中的任何一个为真，则输入为真。

这么说来，我们可以看到我们正在做的是将输入重写为一个大析取，然后列出这些术语。换句话说，您希望将输入重写为Disjunctive normal form。维基百科告诉我们，“所有逻辑公式都可以转换为析取范式。但是，在某些情况下，转换为 DNF 会导致公式的指数爆炸。”

所以：如果你在顶部有一个“或”，返回一组所有的孩子（你可以将此算法递归地应用于每个孩子）。如果您在顶部有一个“与”，则为每个孩子递归地运行它，然后为每个孩子返回“与”选项之一的所有组合。

因此，例如，如果您有 (A|B|C) 给您 A,B,C 作为答案。如果你有 (A & (B|C)) 那么你只得到左孩子的 A 和右孩子的 B,C 。所以把它们放在一起你会得到两个答案：A&B 和 A&C。

如果你有一个“不”，你可以用德摩根定律把它推进去，这样你就可以继续使用上面的两个规则。

PS我正在回答“如何获得所有答案”，这是您的文字所要求的，而不是“如何获得最小的答案”，这是标题所要求的。考虑所有答案并选择最小的答案是一个简单的步骤。

于 2013-07-01T17:49:32.613 回答
0

我想出了以下算法，我认为这可以帮助您Minimal true conditions在表达式中找到 。

eval(X & Y) => eval(X) JOIN eval(Y)
eval(X | Y) => eval(X) MERGE eval(Y)
eval(x) = x

在哪里，

X, Y => 表达式；x => identity
A JOIN B - 列表 A 中的每个元素与列表 B 中的每个元素都使用“&”连接。
A MERGE B - 简单地合并列表 A & B 中的元素

让我们以您的第一个示例为例来证明这一点：表达式 - ((A & B ) & (C | D))。让X -> (A & B)和Y -> (C | D)

现在，

eval(X & Y) => eval(X) JOIN eval(Y)
eval(X) => eval(A) & eval(B) => ['A'] JOIN ['B'] => ['A & B']
eval(Y) => eval(C) MERGE eval(D) => ['C'] MERGE ['D'] => ['C','D']
eval(X & Y) = > ['A & B'] JOIN ['C','D'] => ['A & B & C', 'A & B & D']

类似地，可以整理出其他示例。另外，您在示例 1 中提供的解决方案是错误的，应该如上。

于 2013-07-01T18:42:41.333 回答