# Alternating items in a collection

Is there any better way how to mix items in list? In my example: I want to sort list items as male, female, male, ... My solution is probably very time and resource demanding. Can I do it somehow with LINQ?

private List<Child> MixGender(List<Child> children)
{
List<Child> male = new List<Child>() { };
List<Child> female = new List<Child>() { };

male = children.Where(c => c.Sex == "male").ToList();
female = children.Where(c => c.Sex == "female").ToList();

int childrenCount = children.Count;
int indexMale = 0;
int indexFemale = 0;

children.Clear();

for (int i = 0; i < childrenCount; i++)
{
if (i % 2 == 1)
{
if (indexMale < male.Count)
{
indexMale++;
}
else
{
indexFemale++;
}
}
else
{
if (indexFemale < female.Count)
{
indexFemale++;
}
else
{
indexMale++;
}
}
}

return children;
}

• Could you reframe your question and the requirements? You write about mixing items in lists but then about sorting... I'm very confused. – t3chb0t Nov 8 '18 at 16:25
• I am sorry, English is not my native language. Sorting and mixing is the same thing in this scenario. I would like have every another item different. So in this case 1: male, 2:female, 3:male, 4:female, 5:male etc. My algorithm is working, but I would like to know if it is possible to do it better and faster way. Of course there can be same items on the end- depending on items in List – Tomas Kanok Nov 8 '18 at 17:48
• I follow. It looks OK to me. – paparazzo Nov 8 '18 at 17:50
• ok, now it makes sense, thank you for clarifying this ;-) – t3chb0t Nov 8 '18 at 17:50

It looks like the core of your problem is taking two sequences and "interleaving" them, alternating elements for as long as possible, but allowing for the sequences to be different lengths. Your solution will definitely do that.

BUT. It would be cleaner if you were able to avoid building up a List element-by-element, and if possible also avoid manual index management. My rule of thumb is "If you never access a list by index, you'll never have index-related bugs."

One way to do this would be to use enumerators. Your algorithm could look something like this:

while enumerator A has elements:
yield an element from enumerator A
if enumeratorB has another element:
yield an element from enumerator B

while enumerator B has elements:
yield an element from enumerator B


With this approach, you don't even need to know how many elements there are; you simply "go until you're done".

If I were writing this code, I would probably write it as an extension method, and call it like this:

private List<Child> MixGender(List<Child> children)
{
return children.Where(c => c.Sex == "male")
.Interleave(children.Where(c => c.Sex == "female"))
.ToList();
}

/// <summary>
/// Mix the elements of the two sequences, alternating elements
/// one by one for as long as possible. If one sequence has more
/// elements than the other, its leftovers will appear at the
/// end of the mixed sequence.
/// </summary>
public static IEnumerable<T> Interleave<T>(
this IEnumerable<T> sequenceA,
IEnumerable<T> sequenceB,
)
{
var enumA = sequenceA.GetEnumerator();
var enumB = sequenceB.GetEnumerator();

// As long as there are elements in sequence A
while (enumA.MoveNext())
{
// Take an element from sequence A
yield return enumA.Current;

// And, if possible,
if (enumB.MoveNext())
{
// Take an element from sequence B
yield return enumB.Current;
}
}

// If there are any elements left over in sequence B
while (enumB.MoveNext())
{
// Take each of them
yield return enumB.Current;
}
}


As for the question of time/resource demands: Is the invocation of an extension method, and handling of the enumerators more efficient then manual list creation and management? I would guess so, but I don't know, and I don't particularly care. I would be very confident in guessing that whatever performance gains you make by using one technique over the other will be dwarfed by, for example, the I/O operations your program is making. If (and only if) you notice performance degradation in your application, you should revisit the question with the help of a profiler.

Here is a demonstration comparing the behavior of your original implementation to the enumerator-based technique. They are almost the same but you may want to make some tweaks. It might be a good idea to adapt that demonstration into your unit test suite. Edit: As t3chb0t points out, it is also important to ensure your enumerators are Disposed, which this demo code fails to do.

• this is a nice idea with Interleave and it would be even better if it took a single collection and a comparer to create the two other collections internally. – t3chb0t Nov 8 '18 at 19:46
• One complication that could arise (if we accept a key selector like child => child.Sex and not just a boolean filter) is the possibility of having N groups. That would be an interesting challenge to solve, but I would start to worry about over-engineering. – benj2240 Nov 8 '18 at 20:00
• Challange accepted! I like over-engineering! (ok, as coding-sport, one can learn a lot - not in production) :-] – t3chb0t Nov 8 '18 at 20:19
• ok, this wasn't that difficult... take a look at my edit. – t3chb0t Nov 8 '18 at 20:56

Not a fan of LINQ, yet? Then look here... You could start by grouping Child by Sex into a new lookup, this would replace the two Wheres. In the next step you Zip them together and take one item from each collection at a time. You create from then new tiny collections that you finally flatten with SelectMany. No calculation necessary.

var groups = items.ToLookup(i => i.Sex);
var alternating =
groups["male"]
.Zip(groups["female"], (x, y) => new[] { x, y })
.SelectMany(t => t)
.ToList();


This will however require that both collections have the same length because Zip will go only as far as the shorter collection.

Some nice improvement to you method would be to make it work for any group of items. When you pass it a custom comparer you can GroupBy the items and iterate over each group until there is nothing left to yield. Since enumerators are disposable you need to make sure to dispose them properly at the end thus the finally block.

public static IEnumerable<T> Interleave<T>(this IEnumerable<T> source, IEqualityComparer<T> comparer)
{
var groups = source.GroupBy(x => x, comparer);
var enumerators = groups.Select(g => g.GetEnumerator()).ToList();
try
{
var any = false;
do
{
any = false;
foreach (var e in enumerators)
{
if (e.MoveNext())
{
any = true;
yield return e.Current;
}
}
} while (any);
}
finally
{
foreach (var e in enumerators)
{
e.Dispose();
}
}
}


An example usage could then look like this:

var innerComparer = StringComparer.OrdinalIgnoreCase;
var comparer = EqualityComparerFactory<Child>.Create
(
(x, y) => innerComparer.Equals(x.Sex, y.Sex),
obj => innerComparer.GetHashCode(obj.Sex)
);
var result = items.Interleave(comparer);

• instead of passing in an IEqualityComparer<T> how about a Func<T, TKey> and grouping off of that? Then you don't need EqualityComparerFactory and can still interleave over all the different values of a property. – C.M. Nov 8 '18 at 21:52
• @C.M. I think it would be a good idea to have both APIs because many linq extensions allow you to do it in the one or the other way with the comparer if you need something customized. – t3chb0t Nov 9 '18 at 9:22

My only comment is don't mutate the input and then return it.

private List<Child> MixGender(List<Child> children)


Return a fresh List<Child>.

Male and female should be enum.

• I was just about to mention it ;-] – t3chb0t Nov 8 '18 at 17:57
• ok, now even I wonder why the downvote? This is an important point presented here. – t3chb0t Nov 8 '18 at 18:05
• I don't typically sweat the down votes. I have had way better answers than this get multiple down votes. If I am confused I will ask why but not to argue the down vote. – paparazzo Nov 8 '18 at 19:52
• I think mutating a list is acceptable, but agree it's cleaner to return a fresh list. It would depend on how big the list is and if using a lot of memory was a concern. (I find 99% of lists I deal with are less than 10 items.) -- I would add that if you are going to mutate the list then don't return the list, make the method void (or C# equivalent) to make it clear it's mutating. – Captain Man Nov 9 '18 at 14:50
• yes I noticed it too. How it is possible and why int is not mutating for example? I am not able to google something about "mutate c#" – Tomas Kanok Nov 9 '18 at 15:52

You can avoid building up an inner list in the method using yield returnin the following way:

private IEnumerable<Child> MixGender(List<Child> children)
{
List<Child> male = children.Where(c => c.Sex == "male").ToList();
List<Child> female = children.Where(c => c.Sex == "female").ToList();

int childrenCount = children.Count;
int indexMale = 0;
int indexFemale = 0;

for (int i = 0; i < childrenCount; i++)
{
if (i % 2 == 1)
{
if (indexMale < male.Count)
{
yield return male[indexMale];
indexMale++;
}
else
{
yield return female[indexFemale];
indexFemale++;
}
}
else
{
if (indexFemale < female.Count)
{
yield return female[indexFemale];
indexFemale++;
}
else
{
yield return male[indexMale];
indexMale++;
}
}
}
}