Mischen von zwei Arrays durch abwechselnde Elemente (Reißverschluss-Stil)

Question

Was ist ein eleganter Algorithmus zum Mischen der Elemente in zwei Arrays (von potenziell unterschiedlichen Größen), so dass die Elemente abwechselnd von jedem Array gezeichnet werden, mit den Resten hinzugefügt das Ende?

z.

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

Ich würde die Lösung in C# bevorzugen, aber ich sollte in der Lage sein, Lösungen in jeder Sprache (oder sogar irgendeiner Form von Pseudocode) zu lesen und zu transponieren.

Mach dir keine Sorgen über Null-Prüfung oder andere Randfälle, ich werde mit denen umgehen.

Answer 1

Sie meinen etwas in dieser Richtung?

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

Wenn Sie diese verwenden, werden Sie wahrscheinlich wollen die Array-Längen in Variablen speichern, so dass Sie eine Größe() -Methode nicht halten müssen telefonisch unter (oder was auch immer es in ist, was auch immer Sprache, die Sie verwenden).

Answer 2

Ich sehe einen O (N), N = Größe des größeren Satzes, Algorithmus, da Sie über alle Einträge iterieren müssen.

Answer 3

Es ist eine Funktion, die dies genau funktioniert in der python docs, die

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

kam ich mit einem anderen mit n Arrays arbeitet, der durch die kürzeren Arrays zu wiederholen halten, wenn sie früher aus auszuführen:

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

ich Dilettantismus nur in C#, und als ich zur Zeit über IEnumerable lerne, ich dachte, ich würde versuchen, dieses Problem mit einem Iterator zu lösen.

Der TwoListMerger verwendet zwei Listen als Parameter. Während in beiden Listen einige Werte verarbeitet werden müssen, wechselt er zwischen den einzelnen Listenerträgen und gibt einen Wert zurück. Wenn die eine oder andere Liste erschöpft ist, wechselt der Iterator nicht ab und beendet effizient die Werte der verbleibenden Liste.

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

Ich habe wirklich Spaß mit IEnumerator jetzt!

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

Answer 6

Funktion für PHP (nur mit indizierten Arrays arbeiten):

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

Dank Ryan Graham!