Алгоритм перебора n массивов

[RomikChef]

У меня будет масив но у него каждый элемент МАССИВ!!!!
Дизель, я все понимаю, но нельзя же до ТАКОЙ степени!

 

[_RVK_]

Сори.
Я же сказал что я так и делаю. Скдадываю именно в один масив. В примере который я привйл в самом начале я arr1,arr2... привел в качестве примера, иначе возникли бы вопросы а что там в $main_array. Далее я работаю именно с этим одним масивом каждый элемент которого масив. Но проблему это не снимет. Как получить все возможные комбинации элементов его элементов.

 

[_RVK_]

Кажется получилось:

<?php

//Исходные масивы
$arr1=array('1','2','3','4','5');
$arr2=array('1','2');
$arr3=array('1','2','3','4');

//складываем в один
$main_array=array($arr1,$arr2,$arr3);

//узнаём их количество
$count_arrays=sizeof($main_array);

$col_var=1;
for ($i=0;$i<$count_arrays;$i++)
{
//вычисляем количество возможных вариантов
    $col_var*=sizeof($main_array[$i]);
//счетчик для каждого из масивов. max- максимальное значение счётчика
    $counter[]=array('counter'=>0,'max'=>sizeof($main_array[$i]));
}

$k=0;
$step=0;
//пока все варианты не перебрали
while ($step<$col_var)
{
//по порядку для каждого масива
 for ($i=0;$i<$count_arrays;$i++)
 {
   //если максимальное значение
   if ($counter[$i]['counter']==$counter[$i]['max']-1)
   {
     //то сбрасываем в ноль
     $counter[$i]['counter']=0;
   }
   else //иначе
   {
   //увеличиваем
   $counter[$i]['counter']++;
   //и складываем в масив новую комбинацию
   for ($j=0;$j<$count_arrays;$j++)
   {
	 print '[';
     print $res_array[$step][]=$main_array[$j][$counter[$j]['counter']];
	 print ']';
   }
   print '<br>';
   }

//следуюшяя комбинация
     $step++;
 } // следуюший масив

} //while

?>

 

[Bboy]

Ребята, да это ж МАТРИЦА!!!

 

[_RVK_]

Ребята, да это ж МАТРИЦА!!!

Это не матрица. Все масивы разной длинны.

 

[svdmitrij]

Кажется получилось:

<?php

//Исходные масивы
$arr1=array('1','2','3','4','5');
$arr2=array('1','2');
$arr3=array('1','2','3','4');

//складываем в один
$main_array=array($arr1,$arr2,$arr3);

//узнаём их количество
$count_arrays=sizeof($main_array);

$col_var=1;
for ($i=0;$i<$count_arrays;$i++)
{
//вычисляем количество возможных вариантов
    $col_var*=sizeof($main_array[$i]);
//счетчик для каждого из масивов. max- максимальное значение счётчика
    $counter[]=array('counter'=>0,'max'=>sizeof($main_array[$i]));
}

$k=0;
$step=0;
//пока все варианты не перебрали
while ($step<$col_var)
{
//по порядку для каждого масива
 for ($i=0;$i<$count_arrays;$i++)
 {
   //если максимальное значение
   if ($counter[$i]['counter']==$counter[$i]['max']-1)
   {
     //то сбрасываем в ноль
     $counter[$i]['counter']=0;
   }
   else //иначе
   {
   //увеличиваем
   $counter[$i]['counter']++;
   //и складываем в масив новую комбинацию
   for ($j=0;$j<$count_arrays;$j++)
   {
	 print '[';
     print $res_array[$step][]=$main_array[$j][$counter[$j]['counter']];
	 print ']';
   }
   print '<br>';
   }

//следуюшяя комбинация
     $step++;
 } // следуюший масив

} //while

?>

Большое спасибо!

 

[Armalon]

Идея алгоритма правильная, но вот реализация пострадала. Для тестовых исходныз данных должно быть 40 различных вариаций, а после выполнения кода получаются только 30. Ошибку не нашел еще, когда найду -- укажу

 

[Armalon]

Нашел. Вот этот цикл

   for ($j=0;$j<$count_arrays;$j++)
   {
     print '[';
     print $res_array[$step][]=$main_array[$j][$counter[$j]['counter']];
     print ']';
   }

надо вынести из else и поставить сразу после начала цикла FOR перед комментарием "//если максимальное значение". а то иначе получается что в выборку res_array не попадает часть элементов.

 

[Beavis]

Прошло 9 лет...

 

[Armalon]

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

 

[Armalon]

Вообщем у меня получился такой рекурсивный алгоритм:

function generateVariation($A, $i = 0)
        {
            $result = array();

            if ($i < count($A))
            {
                $variations = generateVariation($A, $i + 1);

                for ($j = 0; $j < count($A[$i]); $j++)
                {
                    if ($variations)
                    {
                        foreach ($variations as $variation)
                        {
                            $result[] = array_merge(array($A[$i][$j]), $variation);
                        }
                    }
                    else
                    {
                        $result[] = array($A[$i][$j]);
                    }
                }
            }

            return $result;
        }

Может кому пригодится

 

[Brainz]

Прошло 8 лет (почти 9)

Спасибо! Это именно то, что я искал

 

[ksnk]

Прошло 8 лет (почти 9)...

_RVK_, 7 май 2003 - первое сообщение топика
svdmitrij, 28 июн 2012 - первый акт некрофилии
Brainz, Вчера, в 01:05 - второй...
в каком месте прошло 8-9 лет ?

 

[Adelf]

ну вот так считают современные школьники.
"6, почти 7" должно было быть, наверно. Что тоже неверно.

 

[c0dex]

Судя по профилю ему 37. Сколько раз на второй год надо было оставаться.

 

[Vladson]

И снова откопали стюардессу. ©

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

 

[Brainz]

Да, ошибся, 6 почти 7. Ребята, спасибо, что открыли глаза, не дали войти в заблуждение. Так бы и помер, не узнав о себе правды. В который раз доказали, поддержка и дружелюбие - вот чем славен рунет.

Для тех, кто попал в этот топик по делу, еще одна функция, она уже работает с массивами с ключами:

function combinations($arrays) {
  $result = array(array());
  foreach ($arrays as $property => $property_values) {
    $tmp = array();
    foreach ($result as $result_item) {
      foreach ($property_values as $property_value) {
        $tmp[] = array_merge($result_item, array($property => $property_value));
      }
    }
    $result = $tmp;
  }
  return $result;
}

$combinations = combinations(
  array(
    'a' => array(1),
    'b' => array(2,3),
    'c' => array(4,5,6),
  )
);