How to performantly get every (unordered) pair of

Question

Example: I have the collection {1, 2, 3, 4}. I want to get all (unordered) pairs of different elements, which are: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}.

If I have an IList, I can do it like this:

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]
        }

For a LinkedList I also know how to do it; it is almost the same except that instead of indexes i and j, we have two LinkedListNodes fst and snd. Whenever we call fst.Next, we will then set snd = fst.Next.

For a list of n elements, the above approach takes (n-1)*n/2 iteration steps. (For i = 0 we have j = 1 ... n-1, so n-1 steps. For i = 1 we have j = 2 ... n-1, so n-2 steps. And so on. This sums up to (n-1) + (n-2) + ... + 3 + 2 + 1 = (n-1)*n/2 steps.)

Is there a way to do it with any ICollection? I thought an IEnumerator could do the trick, but it seems there is no way to tell an IEnumerator "Move to that reference!" like I can do with LinkedListNodes.

EDIT:

I am NOT looking for this solution:

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

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

For a collection of n elements, this approach takes n^2 iteration steps which is a bit more than double than the above approach, so it is clearly not as performant.

EDIT:

Turning the collection into a List beforehand seems to be the easiest way, and the performance penalty is negligible for large n, because it only adds n steps to the whole interation (the new list must be filled by the n elements). So I'll just stick with it.

Answer 1

Edit: Based on the discussion in comments and the edited question it seems that copying the enumerable in a list is the best course of action.

Old answer:

It seems to me that you need to put the items into some kind of hashtable data structure.

Here is a LINQ based solution that uses GroupBy

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);
    }
}

Here each group contains items with the same key (in this example because the item is an int the item is the key but you can group by whatever expression you want)

Alternatively you can group stuff on your own using a dictionary

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

}

In this example I've used a string to emulate a key of int and a value of different type. I think both these solutions are NlogN

Alternatively - sort the collection in a list - all equal elements will be placed one after another. This will be NlogN solution.

Answer 2

IEnumerable is a forward-only iterator; ICollection does not have indexed access. What you could do is get the enumerable into a buffer during the first iteration, and afterwards use the nested for loops.

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]);

Alternatively, if you don't care about going through the items one more time, you could just use enumerable.ToArray() and then use the nested for on that array.