Comparing each element with each other element in a list

Question

What is the best way to write a control structure that will iterate through each 2-element combination in a list?

Example:

{0,1,2}

I want to have a block of code run three times, once on each of these:

{0,1}
{1,2}
{0,2}

I tried the following

foreach (int i in input)
{
    foreach (int j in input.Where(o => o != i))
    {
        //Execute code
    }
}

However, this won't work when a list has two of the same elements. With

{0,2,0}

I would still want to compare elements 0 and 0. The value is irrelevant.

Wertheimer

What are you doing with each of those pairs? Your solution and Jon's solutions are all O(n squared). Depending on what you're doing there might be an O(n) solution. (For example, in the C# compiler you need to compare every pair of methods in an overload resolution problem to determine the unique best method; there is an O(n) algorithm for that even though the better-method relation is intransitive.) – Lyda

Answer 1

It sounds like you might want something like:

for (int i = 0; i < list.Count - 1; i++)
{
    for (int j = i + 1; j < list.Count; j++)
    {
        // Use list[i] and list[j]
    }
}

You definitely can do this with LINQ:

var pairs = from i in Enumerable.Range(0, list.Count - 1)
            from j in Enumerable.Range(i + 1, list.Count - i - 1)
            select Tuple.Create(list[i], list[j]);

I'm not sure it's any clearer though...

EDIT: Another alternative which is less efficient, but potentially clearer:

var pairs = from i in Enumerable.Range(0, list.Count - 1)
            let x = list[i]
            from y in list.Skip(i + 1)
            select Tuple.Create(x, y);

Kevon

Perfect, way simpler than I envisioned. I'll accept when possible. And thank you, but you're right, the LINQ solution is far less readable, and most likely much slower. – Wertheimer

Thanks, the first version (for loop) works like a charm ! However, I think there is something wrong with the second version (LINQ), as it throws me an IndexOutOfRange exception (the index handling is slightly different between the two versions, but I don't have the time to figure out how to fix it). – Vizard

@Ishikawa: I think it was an off-by-one error, which I've now fixed. – Kevon

Answer 2

If you are using C# 7 or later, you can take advantage of the ValueTuple type. It offers increased usability and performance.

public static IEnumerable<(T, T)> GetAllPairs<T>(IList<T> source)
{
    return source.SelectMany((_, i) => source.Where((_, j) => i < j),
        (x, y) => (x, y));
}

Usage example:

foreach ((int x, int y) in GetAllPairs(new[] { 0, 1, 2 }))
{
    // Execute code
    Console.WriteLine($"Pair: {x}, {y}");
}

Output:

Pair: 0, 1
Pair: 0, 2
Pair: 1, 2

Ozell