Mixing two arrays with alternating elements (zipper style)

Question

What is an elegant algorithm for mixing elements in two arrays (potentially of different sizes) so that elements are drawn alternately from each array with the addition of residuals at the end?

eg.

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 a solution in C #, but I would have to read and port solutions in any language (or even in some form of pseudocode).

Do not worry about zero checking or other cases with edges, I will handle them.

Answer 1

Do you mean something like 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 probably want to keep the lengths of the array in variables, so you won’t need to call the size () method (or whatever in any language you use).

Answer 2

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

 from itertools import * def roundrobin(*iterables): "roundrobin('ABC', 'D', 'EF') --> ADEBFC" # 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 continue to repeat through shorter arrays if they end earlier:

 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 3

I am just doing C #, and when I am currently learning IEnumerable, I thought I would try to solve this problem with an iterator.

Two ListMerger accepts two lists as parameters. Although there are some values ​​in any of the lists, they alternate between each list that returns a value. When one or the other list is exhausted, the iterator does not alternate, effectively ending the remaining list 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 4

Function for PHP (only works with indexed arrays):

 function array_merge_alternating(&$array1, &$array2) { $result = array(); $count1 = count($array1); $count2 = count($array2); $i = 0; while (($i < $count1) || ($i < $count2)) { if($i < $count1) array_push($result, $array1[$i]); if($i < $count2) array_push($result, $array2[$i]); $i++; } return $result; } 

Thanks to Ryan Graham!

Answer 5

I see O (N), N = the size of a larger set, an algorithm, since you need to iterate over all the records.

Answer 6

I really have 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; }