Perform operation on each item in a list against every other item in the list with exclusions

Question

I have a list of data with no duplicates. For this example I'll say that my list is

List<string> list1 = new List<string>() { "A", "B", "C", "D" };

I want to perform my operation on each item in the list against every other item in the list except where I already performed my operation on them (A-B and B-A) or if they are the same (A-A).

EG.

A against B
A against C
A against D
B against C
B against D
C against D

Now this is fairly simple to do but my list is very large and this process can be quite time consuming. Also with the data I have I don't need to run the operation on matching data or if the operation has already been run

EG.

A against A - Skip
A against B - Good
A against C - Good
A against D - Good
B against A - Skip (we already did A against B)
B against B - Skip
B against C - Good
B against D - Good
C against A - Skip

and so on.

What I have been looking for (and I don't even know if it exists) is an easy method I can use to do this rather than firing off two loops and doing my operation and saving the results to compare against later.

Looping through the list is O(n*n) but as I don't need to compare over half of the results this is a waste of time as I know that I only need to check O(n*(n/2))

The code I'm currently using is as follows

List<string> list1 = new List<string>() { "A", "B", "C", "D" };
List<string> list2 = new List<string>(list1);
List<string> listResult = new List<string>();

list2.Reverse();

int i = 0;
foreach (var a in list1)
{
    for (int j = 0; j < (list2.Count / 2); j++)
    {
        i++;
        Console.WriteLine("Looped {0} times", i);

        // Don't run against ourself
        if (a == list2[j])
            continue;

        if (listResult.Count(x => (x == a + list2[j]) || (x == list2[j] + a)) == 0)
        {
            listResult.Add(a + list2[j]);

            // Perform some operation here
            // operation(a, list2[j]);
        }
    }
}

The above code works fine (I would need to adjust the list2.Count / 2 part to account for an odd numbered list).

Is there a better way to do this? A LINQ extension method I've missed? My problem is I don't really know what to Google for.

I wondered if there was a method that would return the list just containing the items I wanted which I would then loop through and perform my operation. Maybe something using .SelectMany()

Answer 1

For each entry in the list, match that up to all entries that come after it in the list, since the items before will already have been matched.

List<string> list1 = new List<string>() { "A", "B", "C", "D" };

for( int i = 0; i < list1.Count - 1; i++ )
    for( int j = i + 1; j < list1.Count; j++ )
        Console.WriteLine( "{0} against {1}", list1[i], list1[j] );

Edit: As for your second question, how about something like this:

public static class Extensions
{
    public static IEnumerable<U> Combinations<T, U>( this IEnumerable<T> list,
                                                     Func<T, T, U> combinator )
    {
        var temp = list.ToArray();
        for( int i = 0; i < temp.Length - 1; i++ )
            for( int j = i + 1; j < temp.Length; j++ )
                yield return combinator( temp[i], temp[j] );
    }
}

Which can then be used like this:

List<string> list1 = new List<string>() { "A", "B", "C", "D" };
var res = list1.Combinations( ( a, b ) => string.Format( "{0} against {1}", a, b ) );

If you can live with it supporting just IList instead of any IEnumerable, you could skip the ToArray call completely.