Mixing two arrays by alternating elements (zipper style)

Question

What is an elegant algorithm to mix the elements in two arrays (of potentially differing sizes) so that the items are drawn in an alternating fashion from each array, with the leftovers added to the end?

E.g.

Array 1 - A, B, C, D, E, F, G

Array 2 - 1, 2, 3, 4

Mixed array - A, 1, B, 2, C, 3, D, 4, E, F, G

I would prefer the solution in C#, but I should be able to read and transpose solutions in any language (or even some form of pseudo code).

Don't worry about null checking or any other edge cases, I'll handle those.

Answer 1

You mean something along the lines of this?

// naive/boring approach
int i = 0;
int m = 0;
while (i < a1.size() || i < a2.size()) {
    if (i < a1.size())
        mixed[m++] = a1[i];
    if (i < a2.size())
        mixed[m++] = a2[i];
    i++;
}

If you use this, you'll probably want to store the array lengths in variables so you don't have to keep calling a size() method (or whatever it is in whatever language you use).

Answer 2

I see a O(N), N = size of larger set, algorithm since you have to iterate over all entries.

Answer 3

There is a function that does this exactly in the python docs, which works with n arrays

from itertools import *

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    pending = len(iterables)
    nexts = cycle(iter(it).next for it in iterables)
    while pending:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            pending -= 1
            nexts = cycle(islice(nexts, pending))

I came up with another one that will keep repeating through the shorter arrays if they run out sooner:

from itertools import *    

def repeatrobin(*iterables):
    cycles = cycle(map(cycle, iterables))
    stop = iter(xrange(max(map(len, iterables)) * len(iterables) - 1))
    for c in cycles:
       yield c.next()
       stop.next()

>>> list(repeatrobin(('A', 'B', 'C', 'D', 'E', 'F', 'G'), (1, 2, 3, 4)))
['A', 1, 'B', 2, 'C', 3, 'D', 4, 'E', 1, 'F', 2, 'G', 3]
>>> list(repeatrobin(('A', 'B', 'C', 'D', 'E'), (1, 2, 3), ('*',)))
['A', 1, '*', 'B', 2, '*', 'C', 3, '*', 'D', 1, '*', 'E', 2, '*']

Answer 4

I'm just dabbling in C#, and as I'm currently learning about IEnumerable, I thought I'd try to solve this problem with an iterator.

The TwoListMerger takes two lists as parameters. While there is some values in either list to process, it alternates between each list yield-returning a value. When one or other list is exhausted, the iterator does not alternate, finishing efficiently the remaining list's values.

 public static IEnumerable TwoListMerger( List<object> List1, List<object> List2 )
 {
  // Intialise two indices for the two lists
  int ListIndex1 = 0;
  int ListIndex2 = 0;

  // Begin zipper - List1 will provide the first value, then List2, etc.
  bool YieldFromList1 = true;

  // While values in either list remain...
  while ( ( ListIndex1 < List1.Count ) ||
    ( ListIndex2 < List2.Count ) )  
  {
   // If next value comes from List1...
   if ( YieldFromList1 )
   {
    // Yield from List1 if List2 exhausted( otherwise from List2 )
    YieldFromList1 = ( ListIndex2 >= List2.Count );
    yield return List1[ ListIndex1++ ];
   }
   // Next value comes from List2...
   else
   {
    // Yield from List1 if List1 not exhausted (otherwise from List2)
    YieldFromList1 = ( ListIndex1 < List1.Count );
    yield return List2[ ListIndex2++ ];
   }
  }

  // End iterator
  yield break;
 }


// Example usage (List1 and List2 are lists of integers)
List<object> MergedList = new List<object>( );
foreach ( object o in TwoListMerger( List1, List2 ) )
{
 MergedList.Add( o );
}

foreach ( object o in MergedList )
{
 Console.Write( "{0} ", o.ToString() );
}
Console.WriteLine( "}" );

Answer 5

I'm really having fun with IEnumerator now!

 public static IEnumerable TwoListMerger( List<object> List1, List<object> List2 )
 {
  IEnumerator e1 = List1.GetEnumerator( );
  IEnumerator e2 = List2.GetEnumerator( );

  // Declare here (scope of while test)
  bool b1 = true;
  bool b2 = true;

  // While values remain in either list
  while ( b1 || b2 )
  {
   // NB assignments in "if"s return bool

   // If we have a value remaining in List1, yield return it
   if ( b1 && ( b1 = e1.MoveNext( ) ) )
    yield return e1.Current;

   // If we have a value remaining List2, yield return it
   if ( b2 && ( b2 = e2.MoveNext( ) ) )
    yield return e2.Current;   }

  // Done
  yield break;
 }