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'と'&' represent 'AND'、したがって、大きな条件をすべての可能な最小の真の条件に分割したいと考えています。

提案してください...

4

3 に答える 3

3

したがって、式を単純化して積の合計にする方法があれば、役立つようです。積和形式にすることで、一連の異なるオプションが得られます。含まれるすべての値が true の場合、それぞれが正しい唯一のオプションになります。

これに対処する 1 つの方法は、複合パターンを使用することです。IExpressionインターフェイスから始めます。

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

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

ここでのポイントは、最初と最後の方法です。N 番目の可能性を取得する簡単な方法だけでなく、特定の式にいくつの可能性があるかを知る必要があります。最後のメソッドの規則は、指定されたすべての値が N 番目の可能性に対して真である必要があるということです。2 番目の方法では、外側の列挙型はすべて OR される式であり、内側の式はそれぞれ AND される必要があります。

3つの実装があります。ValueExpressionは 1 つの値のみを表す 、AndExpressionN 個の式を一緒に AND することを表す 、および N個のOrExpression式を一緒に OR することを表す です。

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 演算する必要があります。最初の可能性として、最初のサブ式に 1 を追加します。n が上がるたびに、最初のサブ式から得られる順列を増やします。count を渡すと、0 に戻り、次のサブ式が 1 増えます。これは基本的にカウントに似ていますが、各桁はサブ式の 1 つを表し、その桁の基数はそのサブ式の可能性のカウントです。

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 のようにそれぞれから 1 つを返すのではなく、サブ式の 1 つの可能性の 1 つからのみ項目を返します。

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 式に変更されました (2 番目の例) は次のように表示されます。

AC + BC + AD + BD

3 番目のオプションは次のように表すことができます。

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 に答える
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 => ID
A JOIN B - リスト A のすべての要素がリスト B の各要素と「&」で結合されます。
A MERGE B - リスト A と B の要素を単純にマージします

それを証明するためにあなたの最初の例の例を見てみましょう: Expression - ((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 に答える