Perform an operation on each item in the list for each other item in the list with exceptions

Question

I have a list of data without duplicates. In this example, I will say that my list

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

I want to perform my operation on each element in the list with respect to all other elements in the list, except when I already performed my operation on them (AB and BA), or if they are the same (AA).

EG.

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

Now it’s pretty easy to do, but my list is very long, and this process can be quite time-consuming. Also with the data that I have, I don’t need to start the data matching operation or if the operation is already completed

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 

etc.

What I was looking for (and I don’t even know if it exists) is a simple method that I can use for this, instead of disconnecting the two loops and doing my work and saving the results for comparison with later ones.

Listing through a list of O(n*n) , but since I do not need to compare more than half of the results, this is a waste of time, since I know that I only need to check O(n*(n/2))

The code I use 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 will need to edit list2.Count / 2 part to account for the odd list).

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

I wondered if there was a method that would return a list containing only those elements that I would like to then loop through and complete my operation. Maybe something uses .SelectMany()

Answer 1

For each entry in the list, match all entries that appear after that in the list, since the items have already been matched before.

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

What can be used as follows:

 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 only IList instead of any IEnumerable , you can completely skip the ToArray call.

Answer 2

Just run each item for all items following it in the list.

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

This ensures that no element will be launched by itself or any element with which it has already been launched.

Answer 3

Here we look at all the elements in cascading foreach loops. We add this element only if it does not already exist or if both of them are the same, for example. "AA".

 List<string> list1 = new List<string>() { "A", "B", "C", "D" }; List<string> result = new List<string>(); foreach (string a in list1) foreach (string b in list1) if (!result.Contains(b + a) && a != b) result.Add(a + b); 

Answer 4

I like @Chris to answer yet, if you need to write out the missed operations, this can easily be turned into:

 List<string> list1 = new List<string>() { "A", "B", "C", "D" }; List<string> listResult = new List<string>(); for (int i = 0; i < list1.Count; i++) { for (int k = 0; k < list1.Count; k++) { if (k <= i) { Console.WriteLine("{0} against {1} - Skip", list1[i], list1[k]); } else { Console.WriteLine("{0} against {1} - Good", list1[i], list1[k]); listResult.Add(list1[i] + list1[k]); } } }