如何获取使用数组的任意两个值调用的函数的所有可能值？

Question

考虑以下代码：

class MyClass {
    string PropertyA;
    int PropertyB;
    double PropertyC;
    object PropertyD;
    static ComparisonResult Compare(MyClass a, MyClass b){
        // returns a ComparisonResult with
        // _sampleElement = a
        // _commonProperties = flags that describe the common properties of a and b
    }
}

enum SimilarityFlags {
    SharedPropertyA = 1,
    SharedPropertyB = 2,
    SharedPropertyC = 4,
    SharedPropertyD = 8
}

class ComparisonResult {
    private MyClass _sampleElement;
    private SimilarityFlags _commonProperties;

    bool Equals(object obj){
        ComparisonResult other = obj as ComparisonResult;
        if(other==null) return false;
        if(this._commonProperties != other._commonProperties) return false;
        MyClass s1 = this._sampleElement;
        MyClass s2 = other._sampleElement;
        if(_commonProperties.HasFlag(SimilarityFlags.SharedPropertyA) && s1.PropertyA != s2.PropertyA) return false; 
        if(_commonProperties.HasFlag(SimilarityFlags.SharedPropertyB) && s1.PropertyB != s2.PropertyB) return false; 
        if(_commonProperties.HasFlag(SimilarityFlags.SharedPropertyC) && s1.PropertyC != s2.PropertyC) return false; 
        if(_commonProperties.HasFlag(SimilarityFlags.SharedPropertyD) && s1.PropertyD != s2.PropertyD) return false; 
        return true;
    }

    int GetHashCode(){
        return (int)_commonProperties;
    }
}



MyClass[] array;
HashSet<ComparisonResult> possibleValues = GetAllPossibleComparisonValues(array);

当 Compare 获取数组中的任意两个元素时，如何获取 Compare 返回的所有可能值？

注意：Compare(a, b) == Compare(b, a) 和 a != b

示例（伪代码，3 个属性而不是 4）：

GetAllPossibleComparisonValues( [  {"foo", 5, 0x00}, {"foo", 77, 0x00}, {"BAR", 5, 0x00}, {"foo", 5, 0x00}, {"BAR", 5, 0x00}  ] )

应返回此集合： [ {any, any, 0x00}, {"foo", any, 0x00}, {"foo", 5, 0x00}, {"BAR", 5, 0x00}, {any, 5, 0x00} ]

GetAllPossibleComparisonValues( [ {"foobar", 1}, {"foobar", 2},  {"foobar", 3},  {"foobar", 4} ])

应该返回 [ {"foobar", any} ]

目前，我正在使用此算法：

for(int i = 0; i < array.Length - 1; i++){
    for(int j = i + 1; i < array.Length; j++){
        possibleValues.Add(MyClass.Compare(array[i], array[j]));
    }
}

但效率非常低，特别是对于任意两个元素具有相同 ComparisonResult 的长数组。 计算后，possibleValues.Count 通常非常小 (1..3)，即使对于长数组（2000+ 个元素）也是如此。

我认为可以大大提高计算效率。 例如，如果 Compare(array[0], array[1]) == Compare(array[0], array[2])，则无需调用 Compare(array[1], array[2])

如何我愿意？

Answer 1

这个问题似乎是布尔可满足性问题。如果将数组的每个值建模为布尔输入变量，则可以使用维基百科页面中列出的算法来获取满足特定输出变量的所有输入向量。工作量并不低，所以这取决于您是否真的需要这种加速，或者您是否可以接受现有的工作解决方案，因为这很容易理解。

另一件事可能是您缓存所有已找到的解决方案，并且仅在一个数组中添加了新值时才修改这些找到的向量。这样你只需要先找到解向量。如果您可以应用此取决于天气，则可能的值会经常变化，或者如果它们变化不大。