将一组三个字符串与另一个字符串进行比较

Question

我正在根据一些数据制作一个独特的列表 "set of 3 strings"，如果 3 个字符串放在一起，它们就会成为一个集合，我的列表中只能有独特的集合。

A、B、C
B,C,D
D、E、F 等等

如果列表中不存在集合，我会继续将它们添加到列表中，这样如果我同时遇到这三个字符串 {A,B,C} 我就不会再将它放入列表中。 所以我有 2 个问题。而第二个的答案实际上取决于第一个的答案。

如何存储这组 3 个字符串，使用列表或数组或连接它们或其他任何东西？（我可能会将它添加到字典中以记录它们的计数，但那是以后的事）
如何将一组 3 个字符串与另一个字符串进行比较，而不考虑它们的顺序，显然取决于所使用的结构？我想知道一个正确的解决方案，而不是天真地做所有事情！

顺便说一句，我正在使用C#。

Answer 1

数组或列表是存储数据的最佳选择，因为正如 wentimo 在评论中提到的那样，连接它们意味着您正在丢失可能需要的数据。借用他的例子，"ab" "cd "ef" 串联在一起与 "abcd" "e" 和 "f" 串联相同，但不应被视为等效集.

为了比较它们，我会按字母顺序排列列表，然后按顺序比较每个值。这考虑了值的顺序无关紧要的事实。伪代码示例可能如下所示：

Compare(List<string> a, List<string> b)
{
    a.Sort();
    b.Sort();
    if(a.Length == b.Length)
    {
        for(int i = 0; i < a.Length; i++)
        {
            if(a[i] != b[i])
            {
                return false;
            }
        }
        return true;
    }
    else
    {
        return false;
    }
}

更新

既然您在评论中指出性能是一个重要的考虑因素，因为您可能有数百万个这样的集合要比较并且集合中不会有重复的元素，这里是我的代码的更优化版本，请注意，我不再需要对这两个列表进行排序，这将在执行此功能时节省相当多的时间。

Compare(List<string> a, List<string> b)
{
    if(a.Length == b.Length)
    {
        for(int i = 0; i < a.Length; i++)
        {
            if(!b.Contains(a[i]))
            {
                return false;
            }
        }
        return true;
    }
    else
    {
        return false;
    }
}

DrewJordan 使用哈希表的方法可能仍然比我的方法要好，因为它只需要对每组三个进行排序，然后可以比我的方法更快地与现有集合进行比较。

Answer 2

如果您的集合中不需要重复元素，最好的方法可能是使用 HashSet。听起来每组 3 个都有 3 个独特的元素；如果确实如此，我会将 HashSet 方法与您已经计算出的串联结合起来，即对元素进行排序，与一些分隔符结合，然后将串联的元素添加到 HashSet 中，这将防止重复出现在第一名。

如果您的三组可能有重复的元素，那么就是您必须为每个元素做的事情。对于每三个一组的 HashSet 列表，您可能会获得更好的性能，但是只有三个元素，为可能有数百万个集合的每个元素创建哈希的开销似乎比只迭代一次更糟糕。

Answer 3

这里有一个简单的字符串包装器：

/// The wrapper for three strings
public class StringTriplet
{

    private List<string> Store;

    // accessors to three source strings:
    public string A { get; private set; }
    public string B { get; private set; }
    public string C { get; private set; }

    // constructor (need to feel internal storage)
    public StringTriplet(string a, string b, string c)
    {
        this.Store = new List<string>();
        this.Store.Add(a);
        this.Store.Add(b);
        this.Store.Add(c);
        // sort is reqiured, cause later we don't want to compare all strings each other
        this.Store.Sort();
        this.A = a;
        this.B = b;
        this.C = c;
    }


    // additional method. you could add IComparable declaration to the entire class, but it is not necessary in your task...
    public int CompareTo(StringTriplet obj)
    {
        if (null == obj)
            return -1;

        int cmp;
        cmp = this.Store.Count.CompareTo(obj.Store.Count);
        if (0 != cmp)
            return cmp;

        for (int i = 0; i < this.Store.Count; i++)
        {
            if (null == this.Store[i])
                return 1;

            cmp = this.Store[i].CompareTo(obj.Store[i]);
            if ( 0 != cmp )
                return cmp;
        }

        return 0;
    }

    // additional method. it is a good practice : override both 'Equals' and 'GetHashCode'. See below..
    override public bool Equals(object obj)
    {
        if (! (obj is StringTriplet))
            return false;
        var t = obj as StringTriplet;
        return ( 0 == this.CompareTo(t));
    }

    // necessary method . it will be implicitly used on adding values to the HashSet
    public override int GetHashCode()
    {
        int res = 0;
        for (int i = 0; i < this.Store.Count; i++)
            res = res ^ (null == this.Store[i] ? 0 : this.Store[i].GetHashCode()) ^ i;

        return res;
    }
}

现在您可以创建哈希集并添加值：

var t = new HashSet<StringTriplet> ();

t.Add (new StringTriplet ("a", "b", "c"));
t.Add (new StringTriplet ("a", "b1", "c"));
t.Add (new StringTriplet ("a", "b", "c"));  // dup
t.Add (new StringTriplet ("a", "c", "b"));  // dup
t.Add (new StringTriplet ("1", "2", "3"));
t.Add (new StringTriplet ("1", "2", "4"));
t.Add (new StringTriplet ("3", "2", "1"));

foreach (var s in t) {
    Console.WriteLine (s.A + " " + s.B + " " + s.C);
}
return 0;

Answer 4

您可以继承自 List<String> 并覆盖 Equals() 和 GetHashCode() 方法：

public class StringList : List<String>
{
    public override bool Equals(object obj)
    {
        StringList other = obj as StringList;
        if (other == null) return false;
        return this.All(x => other.Contains(x));
    }
    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 19;
            foreach (String s in this)
            {
                hash = hash + s.GetHashCode() * 31;
            }
            return hash;
        }
    }
}

现在，您可以使用 HashSet<StringList> 仅存储唯一集

将一组三个字符串与另一个字符串进行比较

Compare a set of three strings with another

c#

string

string-comparison

更新