如果随机访问不可用，如何高效地获取每一对（无序的）不同的 collection 元素

Question

示例：我有 collection {1, 2, 3, 4}。我想获得所有（无序）对的不同元素，它们是： {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}.

如果我有 IList，我可以这样做：

IList<MyType> list = ... // fill the list elements

for (int i = 0; i < list.Count - 1; i++)
    for (int j = i+1; j < list.Count; j++)
        {
            ... // now we have the pair of list[i] and list[j]
        }

为了一个LinkedList我也知道怎么做了；它几乎是一样的，除了索引 i 和 j，我们有两个 LinkedListNodes fst 和 snd。每当我们调用 fst.Next 时，我们就会设置 snd = fst.Next.

对于 n 个元素的列表，上述方法需要 (n-1)*n/2 个迭代步骤。（对于i = 0，我们有j = 1 ... n-1，所以n-1步。对于i = 1，我们有j = 2 ... n-1，所以n-2步。等等。这总计 (n-1) + (n-2) + ... + 3 + 2 + 1 = (n-1)*n/2 个步骤。）

有没有办法用 ICollection 做到这一点？我认为 IEnumerator 可以做到这一点，但似乎没有办法告诉 IEnumerator "Move to that reference!" 就像我可以用 LinkedListNodes 做的那样。

编辑：

我不是在寻找这个解决方案：

foreach (MyType a in list)
    foreach (MyType b in list)
    {
        if (a == b)
            continue;

        ... // now we have the pair of a and b
    }

对于 collection 个 n 元素，此方法采用 n^2 迭代步骤，比上述方法多一倍多，因此显然性能不佳。

编辑：

预先将 collection 变成 List 似乎是最简单的方法，而且对于大 n，性能损失可以忽略不计，因为它只增加了 n整个交互的步骤（新列表必须由 n 元素填充）。所以我会坚持下去。

Answer 1

编辑：根据评论中的讨论和编辑后的问题，似乎复制列表中的可枚举项是最好的做法。

旧答案：

在我看来，您需要将这些项目放入某种哈希表数据结构中。

这是一个使用 GroupBy 的基于 LINQ 的解决方案

var items = new List<int> { 1, 2, 3, 2, 3 };

var groupedItems = from i in items
                   group i by i into g
                   select g;

foreach (var group in groupedItems)
{
    //group.Key stores the key of the grouping
    foreach (var item in group) //group contains items with the same key
    {
        //Do something
        Console.WriteLine(item);
    }
}

此处每个组都包含具有相同键的项目（在本例中，因为项目是一个整数，所以项目是键，但您可以按您想要的任何表达式分组）

或者您可以使用字典自行分组

var items = new List<int> { 1, 2, 3, 2, 3 };
var itemsDictionary = new Dictionary<int, List<string>>();

foreach (int i in items)
{
    List<string> repeatedValues;
    if(itemsDictionary.TryGetValue(i, out repeatedValues))
    {
        repeatedValues.Add(i.ToString());
    }
    else
    {
        itemsDictionary.Add(i, new List<string> { i.ToString() });
    }
}

foreach (KeyValuePair<int, List<string>> kvp in itemsDictionary)
{
    //do whatever is needed kvp.Value

}

在这个例子中，我使用了一个字符串来模拟一个 int 键和一个不同类型的值。我认为这两个解决方案都是 NlogN

或者 - 在列表中对集合进行排序 - 所有相等的元素将一个接一个地放置。这将是 NlogN 的解决方案。

Answer 2

IEnumerable 是只进迭代器； ICollection 没有索引访问。您可以做的是在第一次迭代期间将可枚举项放入缓冲区，然后使用嵌套的 for 循环。

var enumerable = Enumerable.Range(0, 10);

var buffer = new List<int>();

using (var enumerator = enumerable.GetEnumerator())
{
    if (enumerator.MoveNext())
    {
        buffer.Add(enumerator.Current);
        while (enumerator.MoveNext())
        {
            var current = enumerator.Current;
            buffer.Add(current);

            Handle(buffer[0], current);
        }
    }
}

for (int i = 1; i < buffer.Count - 1; i++)
    for (int j = i + 1; j < buffer.Count; j++)
        Handle(buffer[i], buffer[j]);

或者，如果您不想再遍历这些项目，您可以只使用 enumerable.ToArray()，然后在该数组上使用嵌套的 for。

如果随机访问不可用，如何高效地获取每一对（无序的）不同的 collection 元素

How to performantly get every (unordered) pair of different collection elements if random access is not available

c#

iteration

ienumerator