Равномерное слияние двух массивов - помогите с алгоритмом

[lantastic]

Равномерное слияние двух массивов - помогите с алгоритмом

Приветствую! Требуется равномерно размешать элементы двух массивов, сохраняя порядок элементов каждого.

То есть, к примеру массив S из 5 элементов, M из 3. Должен получиться массив типа:

S M S S M S M S

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

 

[Crazy]

Элементарно.

<?php

$data1 = array('aaa', 'bbb', 'ccc', 'ddd');
$data2 = array('foo', 'bar', 'buzz', 'fluxx');

function & strange_join($ar1, $ar2) {
  $res = array();
  while (count($ar1) > 0 || count($ar2) > 0) {
    $no = rand(1,2);
    $src = "ar$no";
    if (count($$src) == 0) {
      $no = 3 - $no;
      $src = "ar$no";
    }
    $res[] = array_shift($$src);
  }
  return $res;
}

$res = strange_join($data1, $data2);

var_dump($res);

?>

 

[tony2001]

в чем смысл & ?

 

[Crazy]

Значок красивый.

 

[tony2001]

два лучше смотрятся.
по обе стороны =)

 

[Crazy]

Ха! Ты думаешь, я не пробовал два красивых значка с двух сторон? Но, увы, PHP писали люди лишенные эстетики:

PHP Parse error:  parse error, expecting `'(''

Ну зачем им там эта некрасивая скобка?!

 

[tony2001]

Для эстетов есть Brainfuck - там есть, где разгуляться =)

 

[specialist]

Crazy
поясни в чём смысл & здесь...для чего он нужен?

 

[Crazy]

<?php

function foo() {
  static $foo = array(1,2,3);
  return $foo;
}

function & bar() {
  static $foo = array(1,2,3);
  return $foo;
}

$foo1 =& foo();
$foo2 =& foo();
$bar1 =& bar();
$bar2 =& bar();

$foo1[1] = 100;
$bar1[1] = 100;

var_dump($foo2);
var_dump($bar2);

?>

 

[specialist]

Crazy
пасиб..более-менее понятно стало...

 

[SelenIT]

Crazy
прошу прощения за дурацкий вопрос: как rand(1,2) в предложенном методе справляется с требованием равномерности перемешивания массивов существенно разной длины?

 

[rotoZOOM]

lantastic более менее приемлемый алгоритм на ум пришел.
Пусть даны массивы A и B, пусть |A| - это кол-во элементов первого массива, |B| - количество элементов второго массива.
|A|,|B| > 0

Рассмотрим 2 случая.

1. |A|==1 или |B|==1, тогда для равномерности пишем половину элементов другого массива, потом этот элемент и потом оставшуюся половину друго массива.

2. |A|,|B| > 1, тогда делаем следующим образом:
заводим два счетчика для A и для B, например ai и bi.
Сначала инициализируем их нулями.
Теперь каждый шаг алгоритма.
Если исчерпали все элементы всех массивов, то конец.
Если исчерпали все элементы хотя бы одного массива - то дописываем в конец нового массива оставшиеся элементы другого и конец.
Иначе, смотрим, если ai>bi, то добавляем к новому массиву элемент B[текущий индекс B], текущий индекс B++, bi+=|A|;
иначе добавляем к новому массиву элемент A[текущий индекс A], текущий индекс A++, ai+=|B|;
Проверил - работает нормально.
Но если тебя не удовлетворяет, то ты должен четко определить критерий "равномерности".

 

[SelenIT]

По-моему, все гораздо проще.
Генерируем случайное число от 0 до общего количества элементов в исходных входных массивах.
Если оно меньше исходного количества элементов в $ar1 - выбираем очередной элемент из $ar1, иначе - из $ar2.
Повторяем до тех пор, пока один из массивов не кончится. В конец итогового массива дописываем оставшиеся элементы второго массива.

 

[rotoZOOM]

Это скорее случайный разброс, чем равномерный.

 

[SelenIT]

rotoZOOM

...массив типа:

S M S S M S M S

это случайный или равномерный разброс? Каков твой "критерий равномерности"?
Мой - для произвольного элемента итогового массива вероятность того, что он был выбран из массива А (например), одна и та же независимо от его места в итоговом массиве.

 

[rotoZOOM]

SelenIT IMHO равномерный разброс (точнее смешивание, так как разброс - это уже идет мат.вероятность и статистика) - это когда для любой подпоследовательности конечного массива, содержащей минимум по одному элементу каждого из начальных массивов, выполняется следующее: отношение в ней количества элементов массива с меньшим размером к количеству элементов другого массива будет "не намного" отличаться от отношения общего количества элементов массива с меньшиим размером к общему количествуэлементов другого массива. "Не намного" для грубого подсчета можно взять равным 0.5. А подпоследовательность должна включать минимум один элемент из каждого массива, чтобы деления на 0 не получить.
Вот такая вот каша.

 

[SiMM]

rotoZOOM, а SelenIT что предложил?

 

[rotoZOOM]

SiMM в алгоритме SelenIT нет гарантии того, что будут выполнены приведенные мной условия, так как алгоритм основан на генераторе случайных чисел. Я абсолютно согласен, что если нет четких критериев "равномерного разброса", а достаточно лишь того, что массивы будут перемешаны "на глаз", то и не надо каких-то особо точных алгоритмов.

 

[Crazy]

Автор оригинала: SelenIT
как rand(1,2) в предложенном методе справляется с требованием равномерности перемешивания массивов существенно разной длины?

Есть мнение, что один из нас не понял, чего хотел автор вопроса. И я подозреваю, что этот человек -- не я.