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 Operation on every pair of element in a list), but I'm looking for a .NET solution.

score 4 · Accepted Answer · answered May 14 '10 at 07:57

4

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.

answered May 14 '10 at 07:57

Ian Mercer

38,490
8
97
133

Although several other poster's have given good answers, I like this because it is 1) Concise, 2) Clear (for me), and 3) Clever use of a `SelectMany` override. – Hank May 17 '10 at 14:05

Toby · Answer 2 · 2010-05-14T16:03:50.747

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

This will evaluate each pair twice: once for each order, right? Any way to do this only getting each pair once? — Hank, May 13 '10 at 19:07
See my edit. Alternatively, you could preload the pieces into a `Dictionary` with generated sequential keys, and modify the Linq query appropriately. — Toby, May 14 '10 at 15:52

Daniel Renshaw · Answer 3 · 2010-05-14T07:25:49.387

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

You `Combinations()` and `Permutations()` methods are clever, but they require the generic type `T` to be `IComparable`, which is not ideal. Any other thoughts for generating combinations? Your `Product()` suffers the same problem as @Toby's solution, namely enumerating every unordered pair twice. — Hank, May 13 '10 at 19:56
I've added some overloads that require `IComparer` instead of restricting the type `T`. I've also added a variant of `PairProduct` that acceps a predicate so you can limit the pairs to exactly the ones you want. I've also added the request `ForEachPair` method. — Daniel Renshaw, May 14 '10 at 07:29

Process every pair in a sequence

3 Answers3

Linked