Смешивание двух массивов чередующимися элементами (в стиле молнии)

Question

Что представляет собой элегантный алгоритм для смешивания элементов в двух массивах (потенциально разных размеров), чтобы элементы чередовались из каждого массива поочередно с остатками, добавляемыми в конец?

например.

Массив 1 - A, B, C, D, E, F, G

Массив 2 - 1, 2, 3, 4

Смешанный массив - A, 1, B, 2, C, 3, D, 4, E, F, G

Я бы предпочел решение в C #, но я должен иметь возможность читать и переносить решения на любом языке (или даже в какой-либо форме псевдокода).

Не беспокойтесь о проверке на ноль или любых других крайних случаях, я займусь ими.

Answer 1

Вы имеете в виду что-то подобное?

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

Если вы используете это, вы, вероятно, захотите хранить длины массива в переменных, чтобы вам не приходилось постоянно вызывать метод size () (или как там на каком бы языке вы ни использовали).

Answer 2

Есть функция, которая делает это точно в документах Python , которая работает с n массивами

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

Я придумал еще один, который будет повторяться через более короткие массивы, если они закончатся раньше:

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

Функция для PHP (работает только с индексированными массивами):

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

Спасибо Райану Грэму!

Answer 4

Я просто балуюсь C #, и, поскольку я в настоящее время изучаю IEnumerable, я решил попробовать решить эту проблему с помощью итератора.

TwoListMerger принимает два списка в качестве параметров. Хотя в любом списке есть некоторые значения для обработки, он чередуется между каждым списком, возвращая значение. Когда тот или иной список исчерпан, итератор не чередуется, эффективно заканчивая значения оставшегося списка.

    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

Мне действительно весело с IEnumerator сейчас!

    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

Я вижу алгоритм O (N), N = размер большего набора, так как вам приходится перебирать все записи.