Process every pair in a sequence

Question

I'm looking for a concise way to process every (unordered) pair of elements in a sequence in .NET. I know I can do it with nested for loops, but I was looking for something a little more readable.

I was imagining something like a modified Any() extension method:

IEnumerable<Transaction> transactions = ...
if (transactions.AnyPair( (first, second) => first.UniqueID == second.UniqueID))
    throw ...

Or maybe a foreach-style one:

IEnumerable<JigsawPiece> pieces = ...
pieces.ForEachPair( (first, second) => {
    TryFit(first, second);
});

This question has been asked for other languages (e.g. see http://stackoverflow.com/questions/942543/operation-on-every-pair-of-element-in-a-list), but I'm looking for a .NET solution.

Answer 1

These extension methods will enable you to enumerate every possible pair (following the same naming/conventions outlined in the older SO python question you linked to) and also provides the requested AnyPair method and ForEachPair methods.

public static class EnumerableExtensions
{
    public static bool AnyPair<T>(this IEnumerable<T> values,
        Func<T, T, bool> predicate)
    {
        return values.PairProduct(predicate).Any();
    }

    public static void ForEachPair<T>(this IEnumerable<T> values,
        Action<T, T> action)
    {
        foreach (Tuple<T, T> pair in values.PairProduct())
        {
            action(pair.Item1, pair.Item2);
        }
    }

    public static void ForEachPair<T>(this IEnumerable<T> values,
        Action<T, T> action, Func<T, T, bool> predicate)
    {
        foreach (Tuple<T, T> pair in values.PairProduct(predicate))
        {
            action(pair.Item1, pair.Item2);
        }
    }

    public static IEnumerable<Tuple<T, T>> PairProduct<T>(
        this IEnumerable<T> values)
    {
        return from value1 in values
               from value2 in values
               select Tuple.Create(value1, value2);
    }

    public static IEnumerable<Tuple<T, T>> PairProduct<T>(
        this IEnumerable<T> values, Func<T, T, bool> predicate)
    {
        return from value1 in values
               from value2 in values
               where predicate(value1, value2)
               select Tuple.Create(value1, value2);
    }

    public static IEnumerable<Tuple<T, T>> PairPermutations<T>(
        this IEnumerable<T> values) where T : IComparable<T>
    {
        return from value1 in values
               from value2 in values
               where value1.CompareTo(value2) != 0
               select Tuple.Create(value1, value2);
    }

    public static IEnumerable<Tuple<T, T>> PairPermutations<T>(
        this IEnumerable<T> values, IComparer<T> comparer)
    {
        return from value1 in values
               from value2 in values
               where comparer.Compare(value1, value2) != 0
               select Tuple.Create(value1, value2);
    }

    public static IEnumerable<Tuple<T, T>> PairCombinations<T>(
        this IEnumerable<T> values) where T : IComparable<T>
    {
        return from value1 in values
               from value2 in values
               where value1.CompareTo(value2) < 0
               select Tuple.Create(value1, value2);
    }

    public static IEnumerable<Tuple<T, T>> PairCombinations<T>(
        this IEnumerable<T> values, IComparer<T> comparer)
    {
        return from value1 in values
               from value2 in values
               where comparer.Compare(value1, value2) < 0
               select Tuple.Create(value1, value2);
    }
}

Answer 2

Linq! Full outer join:

        IEnumerable<JigsawPiece> pieces = new List<JigsawPiece>();

        var allPairs =
            from p1 in pieces
            from p2 in pieces
            where !ReferenceEquals(p1, p2)

            // edit
                && pieces.IndexOf(p1) < pieces.IndexOf(p2)
            // endedit

            select new { p1, p2 };

        foreach (var pair in allPairs)
        {
            TryFit(pair.p1, pair.p2);
        }

Edit to add an actual extension method implementation:

    public static void ForEachPair<T>(this IEnumerable<T> source, Action<T, T> action)
    {
        int index = 0;

        var dictionary = source.ToDictionary(t => index++);

        var distinctPairs =
            from kvp1 in dictionary
            from kvp2 in dictionary
            where kvp1.Key < kvp2.Key
            select new { T1 = kvp1.Value, T2 = kvp2.Value };

        foreach (var pair in distinctPairs)
        {
            var copy = pair;
            action(copy.T1, copy.T2);
        }
    }

Answer 3

var query = transactions
             .SelectMany((val1,j) => transactions.Select((val2,i) => new {v1=val1, v2=val2, i=i, j=j}))
             .Where(x => x.i < x.j);

var result = query.Select(x=> x.v1.UniqueID == x.v2.UniqueID);

This performs the comparison the correct number of times. The result also includes the indexes i, j of the two elements that matched.