# Partitioning a sequence into sublists

This function divides a sequence into partitions, where a partition is a list of consecutive matching elements.

Example

Input: (A, A, B, B, B, A, C, C)

Output: ((A, A), (B, B, B), (A), (C, C))

I've tried to make this code "obviously correct", but it still doesn't look that way to me.

public static IEnumerable<List<T>> PartitionBy<T, PK>(this IEnumerable<T> sequence, Func<T, PK> partitionKey)
{
return sequence.PartitionBy(partitionKey, EqualityComparer<PK>.Default);
}

public static IEnumerable<List<T>> PartitionBy<T>(this IEnumerable<T> sequence, IEqualityComparer<T> comparer)
{
return sequence.PartitionBy(item => item, comparer);
}

public static IEnumerable<List<T>> PartitionBy<T, X>(this IEnumerable<T> sequence, Func<T, X> partitionKey, IEqualityComparer<X> comparer)
{
var itr = sequence.GetEnumerator();
if (!itr.MoveNext())
{
// empty sequence was passed in, so return empty sequence
yield break;
}

// Start the first partition.
var currentList = new List<T>(new[] { itr.Current });

while (itr.MoveNext())
{
var key1 = partitionKey(currentList[0]);
var key2 = partitionKey(itr.Current);

if (comparer.Equals(key1, key2))
{
// continue current partition
}
else
{
// yield current partition and start a new one
yield return currentList;
currentList = new List<T>(new[] { itr.Current });
}
}

// We know it has at least 1 element here.
yield return currentList;
}

• A downvote less than 5 seconds after posting? – default.kramer May 31 '17 at 18:50
• The close-voter picked "unclear what you're asking" for a close reason; I suppose your post could use an edit to clarify what your code is doing, how it's used and why there are 3 overloads. – Mathieu Guindon May 31 '17 at 19:01
• And how you mean that the code doesn't look "obviously correct"? – Simon Forsberg May 31 '17 at 19:04
• I think that the poster is saying that the code works correctly, but is too verbose to be intuitively understood. – 200_success May 31 '17 at 19:14
• @BKSpurgeon - GroupBy doesn't work because non-consecutive items end up in the same group. See my example, how one of the partitions is (A, A) and another is (A) – default.kramer Jun 1 '17 at 14:16

Just a small point to start:

new List<T>(new[] { itr.Current });


You don't need the array too, you can just do:

new List<T> { itr.Current };


I'd suggest that you aim for consistency with your generic type names too. Why X vs PK? I'd suggest TKey for both.

You could do it just with a foreach:

public static IEnumerable<IEnumerable<T>> Partition<T, TKey>(
this IEnumerable<T> items,
Func<T, TKey> keySelector,
IEqualityComparer<TKey> comparer)
{
List<T> currentPartition = null;
foreach (var item in items)
{
if (currentPartition != null
&& comparer.Equals(keySelector(item), keySelector(currentPartition[0])))
{
}
else
{
if (currentPartition != null)
{
yield return currentPartition;
}
currentPartition = new List<T> { item };
}
}
if (currentPartition != null)
{
yield return currentPartition;
}
}


Is it clearer than your code? I'm not convinced it is.

• Despite the (relative) complexity inside the loop, I do think this will be clearer for most programmers, simply because it avoids the cumbersome enumerator code that foreach is meant to free us from. – VisualMelon May 31 '17 at 21:35
• Yeah, I started with a foreach but it wasn't as clean as yours. I think I slightly prefer yours to my OP now. And naming it "currentPartition" is a big improvement over "currentList". – default.kramer May 31 '17 at 22:13