Pair-wise iteration in C#, or sliding window enumerator

Question

If I have an IEnumerable like:

string[] items = new string[] { "a", "b", "c", "d" };

I would like to loop thru all the pairs of consecutive items (sliding window of size 2). Which would be

("a", "b"), ("b", "c"), ("c", "d")

My solution was is this

    public static IEnumerable<Pair<T, T>> Pairs(IEnumerable<T> enumerable) {
        IEnumerator<T> e = enumerable.GetEnumerator(); e.MoveNext();
        T current = e.Current;
        while ( e.MoveNext() ) {
            T next = e.Current;
            yield return new Pair<T, T>(current, next);
            current = next;
        }
    }
   
 // used like this :
 foreach (Pair<String,String> pair in IterTools<String>.Pairs(items)) {
    System.Out.PrintLine("{0}, {1}", pair.First, pair.Second)
 }

When I wrote this code, I wondered if there are already functions in the .NET framework that do the same thing and do it not just for pairs but for any size tuples. IMHO there should be a nice way to do this kind of sliding window operations.

_{I use C# 2.0 and I can imagine that with C# 3.0 (using LINQ) there are more and nicer ways to do this, but I'm primarily interested in C# 2.0 solutions. Though, I will also appreciate C# 3.0 solutions.}

Answer 1

In .NET 4 this becomes even easier:-

var input = new[] { "a", "b", "c", "d", "e", "f" };
var result = input.Zip(input.Skip(1), (a, b) => Tuple.Create(a, b));

Answer 2

Rather than require a tuple (pair) type, why not just accept a selector:

public static IEnumerable<TResult> Pairwise<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TSource, TResult> resultSelector)
{
    TSource previous = default(TSource);

    using (var it = source.GetEnumerator())
    {
        if (it.MoveNext())
            previous = it.Current;

        while (it.MoveNext())
            yield return resultSelector(previous, previous = it.Current);
    }
}

Which allows you to skip the intermediate object if you want:

string[] items = new string[] { "a", "b", "c", "d" };
var pairs = items.Pairwise((x, y) => string.Format("{0},{1}", x, y));

foreach(var pair in pairs)
    Console.WriteLine(pair);

Or you can use an anonymous type:

var pairs = items.Pairwise((x, y) => new { First = x, Second = y });

Update: I just implemented this on a real project and used C# 7.0 ValueTuple instead:

public static IEnumerable<(T, T)> Pairwise<T>(this IEnumerable<T> source)
{
    var previous = default(T);
    using (var it = source.GetEnumerator())
    {
        if (it.MoveNext())
            previous = it.Current;

        while (it.MoveNext())
            yield return (previous, previous = it.Current);
    }
}

Answer 3

The easiest way is to use ReactiveExtensions

using System.Reactive;
using System.Reactive.Linq;

and make yourself an extension method to kit bash this together

public static IEnumerable<IList<T>> Buffer<T>(this IEnumerable<T> seq, int bufferSize, int stepSize)
{
    return seq.ToObservable().Buffer(bufferSize, stepSize).ToEnumerable();
}

Answer 4

Just for convenience, here is a selector-less version of @dahlbyk's answer.

public static IEnumerable<Tuple<T, T>> Pairwise<T>(this IEnumerable<T> enumerable)
{
    var previous = default(T);

    using (var e = enumerable.GetEnumerator())
    {
        if (e.MoveNext())
            previous = e.Current;

        while (e.MoveNext())
            yield return Tuple.Create(previous, previous = e.Current);
    }
}

Answer 5

A little late to the party, but as an alternative to all these extension methods, one might use an actual "sliding" Collection to hold (and discard) the data.

Here is one I ended up making today:

public class SlidingWindowCollection<T> : ICollection<T>
{
    private int _windowSize;
    private Queue<T> _source;

    public SlidingWindowCollection(int windowSize)
    {
        _windowSize = windowSize;
        _source = new Queue<T>(windowSize);
    }

    public void Add(T item)
    {
        if (_source.Count == _windowSize)
        {
            _source.Dequeue();
        }
        _source.Enqueue(item);
    }

    public void Clear()
    {
        _source.Clear();
    }

    ...and just keep forwarding all other ICollection<T> methods to _source.
}

Usage:

int pairSize = 2;
var slider = new SlidingWindowCollection<string>(pairSize);
foreach(var item in items)
{
    slider.Add(item);
    Console.WriteLine(string.Join(", ", slider));
}

Answer 6

Here is my solution using a Stack. It is short and concise.

string[] items = new string[] { "a", "b", "c", "d" };

Stack<string> stack = new Stack<string>(items.Reverse());

while(stack.Count > 1)
{
  Console.WriteLine("{0},{1}", stack.Pop(), stack.Peek());
}

You can take the same concept and use a queue which avoids the need for reversing the items and is even simpler:

var queue = new Queue<string>(items);

while (queue.Count > 1)
{
   Console.WriteLine("{0},{1}", queue.Dequeue(), queue.Peek());
}

A short word about performance:

I believe it's important to realize that unless you know that a task is causing a bottleneck in your real application, it's probably not worth working out what the truly fastest way of doing is. Instead, write the code which does the job for you. Also, use code you can remember, so it easily flows out of your hand the next time you need it.

Nevertheless, in case you care for some performance data for 10.000.000 random strings:

Run #1
  InputZip             00:00:00.7355567
  PairwiseExtension    00:00:00.5290042
  Stack                00:00:00.6451204
  Queue                00:00:00.3245580
  ForLoop              00:00:00.7808004
  TupleExtension       00:00:03.9661995

Run #2
  InputZip             00:00:00.7386347
  PairwiseExtension    00:00:00.5369850
  Stack                00:00:00.6910079
  Queue                00:00:00.3246276
  ForLoop              00:00:00.8272945
  TupleExtension       00:00:03.9415258

Tested using Jon Skeet's micro benchmarking tool.

If you want to take a look at the source for the test go here: gist here

Answer 7

Something like this:

public static IEnumerable<TResult> Pairwise<T, TResult>(this IEnumerable<T> enumerable, Func<T, T, TResult> selector)
{
    var previous = enumerable.First();
    foreach (var item in enumerable.Skip(1))
    {
        yield return selector(previous, item);
        previous = item;
    }
}

Answer 8

Forgive me if I'm overlooking something, but why not something simple, like a for loop?:

public static List <int []> ListOfPairs (int [] items)
{
    List <int> output = new List <int>();
    for (int i=0; i < items.Length-1; i++)
    {
        Int [] pair = new int [2];
        pair [0]=items [i];
        pair [1]=items [i+1];
        output.Add (pair);
    }
    return output;
}

Answer 9

Expanding on the previous answer to avoid of O(n²) approach by explicitly using the passed iterator:

public static IEnumerable<IEnumerable<T>> Tuples<T>(this IEnumerable<T> input, int groupCount) {
  if (null == input) throw new ArgumentException("input");
  if (groupCount < 1) throw new ArgumentException("groupCount");

  var e = input.GetEnumerator();

  bool done = false;
  while (!done) {
    var l = new List<T>();
    for (var n = 0; n < groupCount; ++n) {
      if (!e.MoveNext()) {
        if (n != 0) {
          yield return l;
        }
        yield break;
      }
      l.Add(e.Current);
    }
    yield return l;
  }
}

For C# 2, before extension methods, drop the "this" from the input parameter and call as a static method.

Answer 10

C# 3.0 solution (sorry:)

public static IEnumerable<IEnumerable<T>> Tuples<T>(this IEnumerable<T> sequence, int nTuple)
{
    if(nTuple <= 0) throw new ArgumentOutOfRangeException("nTuple");

    for(int i = 0; i <= sequence.Count() - nTuple; i++)
        yield return sequence.Skip(i).Take(nTuple);
}

This isn't the most performant in the world, but it's sure pleasant to look at.

Really, the only thing making this a C# 3.0 solution is the .Skip.Take construct, so if you just change that to adding the elements in that range to a list instead, it should be golden for 2.0. That said, it's still not performant.

Answer 11

The F# Seq module defines the pairwise function over IEnumerable<T>, but this function is not in the .NET framework.

If it were already in the .NET framework, instead of returning pairs it would probably accept a selector function due to the lack of support for tuples in languages like C# and VB.

var pairs = ns.Pairwise( (a, b) => new { First = a, Second = b };

I don't think any of the answers here really improve on your simple iterator implementation, which seemed the most natural to me (and the poster dahlbyk by the looks of things!) too.

Answer 12

Alternate Pairs implementation, using last pair to store previous value:

static IEnumerable<Pair<T, T>> Pairs( IEnumerable<T> collection ) {
  Pair<T, T> pair = null;
  foreach( T item in collection ) {
    if( pair == null )
      pair = Pair.Create( default( T ), item );
    else
      yield return pair = Pair.Create( pair.Second, item );
  }
}

Simple Window implementation (only safe for private use, if caller does not save returned arrays; see note):

static IEnumerable<T[]> Window( IEnumerable<T> collection, int windowSize ) {
  if( windowSize < 1 )
    yield break;

  int index = 0;
  T[] window = new T[windowSize];
  foreach( var item in collection ) {
    bool initializing = index < windowSize;

    // Shift initialized window to accomodate new item.
    if( !initializing )
      Array.Copy( window, 1, window, 0, windowSize - 1 );

    // Add current item to window.
    int itemIndex = initializing ? index : windowSize - 1;
    window[itemIndex] = item;

    index++;
    bool initialized = index >= windowSize;
    if( initialized )
      //NOTE: For public API, should return array copy to prevent 
      // modifcation by user, or use a different type for the window.
      yield return window;
  }
}

Example use:

for( int i = 0; i <= items.Length; ++i ) {
  Console.WriteLine( "Window size {0}:", i );
  foreach( string[] window in IterTools<string>.Window( items, i ) )
    Console.WriteLine( string.Join( ", ", window ) );
  Console.WriteLine( );
}

Answer 13

I created a slightly modified version of the late-2020-updated code in @dahlbyk's answer. It is better suited for projects with nullable reference types enabled (<Nullable>enable</Nullable>). I also added basic docs.

/// <summary>
/// Enumerates over tuples of pairs of the elements from the original sequence. I.e. { 1, 2, 3 } becomes { (1, 2), (2, 3) }. Note that { 1 } becomes { }.
/// </summary>
public static IEnumerable<(T, T)> Pairwise<T>(this IEnumerable<T> source)
{
    using var it = source.GetEnumerator();
        
    if (!it.MoveNext())
        yield break;

    var previous = it.Current;

    while (it.MoveNext())
        yield return (previous, previous = it.Current);
}

Answer 14

This will make a single pass through the IEnumerable.

items.Aggregate(new List<string[]>(), (list, next) => { if (list.Count > 0) list[^1][1] = next; list.Add(new[] { next, next }); return list; }, (list) => { list.RemoveAt(list.Count -1); return list; });

Answer 15

New C# language allows to do something like this:

        var pairlist = new (string, string)[] { ("a", "b"), ("b", "c"), ("c", "d") };

        foreach (var pair in pairlist)
        {
            //do something with pair.Item1 & pair.Item2