通过传递关系检查一个对象是否等于另一个对象

Bert Wagner 发表于 Dev

伯特·瓦格纳

我有一个ValuePair类，其中定义了两个属性：

public class ValuePair: IEquatable<ValuePair>
{
    public string value1;
    public string value2;

    public ValuePair(string v1, string v1)
    {
        this.value1 = v1;
        this.value2 = v2;
    }
    ...
}

我在列表中定义了一些测试数据，如下所示：

List<ValuePair> pairs = new ValuePair<ValuePair>();
pairs.Add(new ValuePair("A","B"));
pairs.Add(new ValuePair("A","C"));
pairs.Add(new ValuePair("B","C"));
pairs.Add(new ValuePair("C","D"));

我的目标是保留对[0]和对[1]，因为对“ A，B”和“ A，C”是唯一的，但是要删除对[2]，因为已经捕获了关系“ B，C”在前两个关系中。对[3]应该保留，因为“ C，D”关系是唯一的。

我觉得这个问题的解决方案将是递归的，这是我很少有的经验。我开始尝试向ValuePair类添加方法，该方法看起来像这样：

public string EqualToEither(ValuePair v)
        {
            if (v.value1 == this.value1 || v.value1 == this.value2)
                return v.value1;
            else if (v.value2 == this.value1 || v.value2 == this.value2)
                return v.value2;
            else
                return string.Empty;
        }

我已经开始尝试在这样的函数中使用上述方法，但是我开始迷恋下一步要做的事情：

 for (int i = 0; i < pairs.Count; i++)
        {
            for (int j = pairs.Count - 1; j >= 0; j--)
            {
                if (pairs[j].EqualToEither(pairs[i]) != string.Empty)
                {
                    pairs[j].EqualToEither(pairs[i]);
                }
                else
                {
                    continue;
                }
            }
        }

我觉得自己已经接近，但仍然无法实现。有人可以提供一些指导吗？如果我要以完全错误的方式处理此问题，请告诉我，谢谢！

库甘斯

最近我不得不解决一个类似的问题，这是我解决的方法：

我认为，通过将相互关联的元素组合在一起，可以最好地表示可传递性。

对于每一对，您必须验证它是否已经属于一个组（两个值都已在组中）或是否扩展了组的关系（只有一个值属于该组）。

如果它不属于任何组，它将成为一个新组。

如果两个值都属于不同的组，则必须将它们合并。

如前所述，这与生成树密切相关。

一种解决方案是使用HashSets来表示您的关系的可传递性（我没有使用HashSets，有很多可能的解决方案）。每个HashSet将代表一组相互关联的元素。

使用HashSets的示例实现：

List<ValuePair> pairs = new List<ValuePair>();
pairs.Add(new ValuePair("A", "B"));
pairs.Add(new ValuePair("A", "C"));
pairs.Add(new ValuePair("B", "C"));
pairs.Add(new ValuePair("C", "D"));

List<ValuePair> uniquePairs = new List<ValuePair>(); 
// this list is not really needed if all you care about 
//   is getting the resulting groups

List<HashSet<string>> sets = new List<HashSet<string>>();

foreach (ValuePair pair in pairs)
{
    int value1Set = -1;
    int value2Set = -1;

    for (int i = 0; i < sets.Count; i++)
    {
        HashSet<string> set = sets[i];

        if (set.Contains(pair.value1))
            value1Set = i;
        if (set.Contains(pair.value2))
            value2Set = i;
    }

    if (value1Set == -1 && value2Set == -1)
    {
        // we have a new set
        sets.Add(new HashSet<string> {pair.value1, pair.value2});
    }
    else if (value1Set == -1)
    {
        sets[value2Set].Add(pair.value1);
    }
    else if (value2Set == -1)
    {
        sets[value1Set].Add(pair.value2);
    }
    else
    {
        if (value1Set == value2Set)
        {
            // duplicate entry, skip the add
            continue;
        }

        // merge the sets at value1Set and value2Set
        foreach (string value in sets[value2Set])
        {
            sets[value1Set].Add(value);
        }
        sets.RemoveAt(value2Set);
    }

    uniquePairs.Add(pair);
}