Iterating over unordered pairs of elements stored in a collection

In C#, I have got a collection of unique elements and I wa开发者_高级运维nt to efficeiently execute some code for each unordered pair. For instance, if my container holds {a,b,c}, the unordered pairs are (a,b), (a,c) and (b,c). The problem arises in the scope of performing a 2-opt optimization, thus efficency is an issue.

• My current solution looks like:

  foreach(var a in container) 
  {
      foreach(var b in container)
      {
          if (a < b)
          {
               // execute code    
          }
      }
   }
  

  Obviously, this can be modified easily if the operator [] is available to get the i-th element (i.e. if the underlying data structure is a list.) But for all other containers, the solution is dependent on the existence of some comparison function and not very efficient.

• I've also tried a formulation based on a LINQ statement that generates each desired pair exactly once. However, as expected, this was much slower than the first approach. This applies to a solution using ElementAt too.

Edit: here is the (improved) LINQ code that was used:

var x = from a in container
        from b in container
        where a < b 
        select new KeyValuePair<int,int>(a,b);

Still, execution is slower by a factor of 3-5 compared to the other solutions.

• Here is the way I would do it in C++ (obtaining good efficiency):

  for(auto it1 = container.begin(); it1!=container.end(); ++it1) 
  {
      auto it2 = it1;
      for(++it2; it2!=container.end(); ++it2) 
      {
          // execute code    
      }
   }
  

  Unfortunatelly, to transform this into C#, it would be required to clone the (internally used) Enumerator, which is not supported by the language itself.

Has anyone a better idea / solution?

Did you try to copy the elements into a list first and then do the algorithm with the indexer ([i]) operator? Since the algorithm has quadratic runtime anyways it may be negligible to have a linear copy operation in front of it. You would have to find out the actual runtime for small, middle and large containers yourself...

I think it may be worth a try, this may well be a lot faster than working with the comparison operator each time.

You could also check if the container is of type IList<T> and jump past the copy operation.

If you don't care about the order, you can do it like this:

int i = 0;
foreach (var a in list)
{
    int j = 0;
    foreach (var b in list)
    {
        if (i <= j)
            break;

        // execute code    

        j++;
    }

    i++;
}

If you do care about the order, you can limit yourself to collections that implement IList<T>, which contains the [] operator. Or you could copy the collection into a List<T> first, and then work with that.

Enumerators in C# are not the same with C++ enumerators from your question. In C# you have neither begin nor end elements of container. You only have Current element and Next() method. It allows you to yield much more sequences, for example - you can enumerate through infinity sequence of random numbers, which obviously has not begin or end.

So - you can't do it in C# like in your C++ code using only IEnumerable classes. The best way to do it is to use System.Collection.Generics.IList<T> interface. Many of types (such as arrays) inherit this interface.

If you use IEnumerable then inside your type you (in most cases) iterate through some collection. If you do this - you can just implement IList<T> interface.

There is another solution - in C# lists and arrays of reference types contains only reference to object. So - you can copy your data to local list and operate with it. But it depends on your memory and performance requirements.

Put your items into a List or IList, and then you can access them using indices in a very similar pattern to your C++ code.

for (int i = 0; i < container.Count(); i++)
for (int j = i+1; j < container.Count(); j++)
{
    var item1 = container.Item[i];
    var item2 = container.Item[j];
}

I'd expect it to be more efficient to iterate an ordered collection using indices rather than the n^2 comparisons. The efficiency of the comparison operator is important but you shouldn't need to compare at all.