Alternating items in a collection

Question

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)
                {
                    children.Add(male[indexMale]);
                    indexMale++;
                }
                else
                {
                    children.Add(female[indexFemale]);
                    indexFemale++;
                }
            }
            else
            {
                if (indexFemale < female.Count)
                {
                    children.Add(female[indexFemale]);
                    indexFemale++;
                }
                else
                {
                    children.Add(male[indexMale]);
                    indexMale++;
                }
            }
        }

        return children;
    }

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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