За последние 24 часа нас посетили 11360 программистов и 602 робота. Сейчас ищут 133 программиста ...

Как пересечь каждый элемент многомерного массива с каждым другим?

Тема в разделе "Решения, алгоритмы", создана пользователем Forward5, 23 фев 2021.

  1. Forward5

    Forward5 Новичок

    С нами с:
    5 фев 2021
    Сообщения:
    11
    Симпатии:
    0
    Приветствую, уже 2 дня туплю над реализацией казалось бы простой функции...
    на вход поступает массив массивов произвольной длины, типа
    {
    a=>[1,2,3,4],
    b=>[00,aa],
    c=>[F]
    }

    На выходе нужно получить такое (порядок не важен):
    {
    1 00 F,
    1 aa F,
    2 00 F,
    2 aa F,
    3 00 F,
    ... и так далее }

    т.е. нужно получить все возможнные комбинации элементов всех переданных массивов.

    Никак не пойму как правильно завернуть это в циклы... Смог родить такое:
    PHP:
    1. function Multiply ($inputarray){
    2. $result=array();
    3. $prevRes=array();
    4. foreach ($inputarray as $column=>$list){
    5. if(!empty($prevRes)){
    6.         foreach ($list as $row) { //перебираем список
    7.                     foreach ($prevRes as  $line){//перебираем уже записанный результат
    8.                     $newline=(string) $line.' | '.$row;
    9. //var_dump($newline);
    10.                      //перемножаем с тем что есть
    11.                     $result[]=$newline;
    12.                 }
    13.                 $prevRes=$result;
    14.                $result=array();
    15.  
    16.                 }
    17.  
    18.                 } else //первый столбец
    19.  
    20.                     $prevRes=$list;
    21.  
    22.  
    23.             }
    24.  
    25.  
    26.     return $prevRes;
    27. }
    Но это неправильно. выводит :
    [0]=>
    string(15) "1 | 00 | aa | F"
    [1]=>
    string(15) "2 | 00 | aa | F"
    [2]=>
    string(15) "3 | 00 | aa | F"
    [3]=>
    string(15) "4 | 00 | aa | F"

    т.е. несколько элементов 1 массива попадают в 1 результирующую строку.. что ожидаемо, раз у меня идет перебор всех элементов каждого массива... Но блин, не могу понять как иначе сделать... пробовал переписать через for - но прихожу к тому же самому..
     
  2. Drunkenmunky

    Drunkenmunky Новичок

    С нами с:
    12 авг 2020
    Сообщения:
    763
    Симпатии:
    139
    Сначала объедините значения двух массивов в новый массив.
    Новый массив "объедините" с третьим в другой новый массив.
     
  3. Forward5

    Forward5 Новичок

    С нами с:
    5 фев 2021
    Сообщения:
    11
    Симпатии:
    0
    Так я же так и делал ведь!
    Значит все правильно было. Да, просто ошибся во вложенности форычей - а так все верно.
    Ок, спасибо. Получился такой код правильный:
    PHP:
    1. function Multiply($inputarray){ //input array of column arrays
    2.     $result=array();
    3.  
    4. $prevRes=array(); // 1 column
    5.  
    6. foreach ($inputarray as $column=> $list) {
    7.   if(empty($result)){
    8. $result=$list;
    9.  
    10.   } else{
    11. foreach ($result as $line) {
    12.   foreach ($list as $row) {
    13.    $newline=(string) $line.'|'.(string)$row;
    14.    $prevRes[]=$newline;
    15.   }
    16.  }
    17.  
    18. $result=$prevRes;
    19. $prevRes=array();
    20. }
    21.  
    22. }
    23.  
    24. return $result;
    25.  
    26. }
     
  4. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.501
    Симпатии:
    599
    На тысяче элементов такой алгоритм займёт слишком много времени.
    Предлагаю расписать на бумаге все варианты в три строки и найти закономерность. Для наглядности лучше чтобы не было членов со всего одним вариантом.
     
  5. Drunkenmunky

    Drunkenmunky Новичок

    С нами с:
    12 авг 2020
    Сообщения:
    763
    Симпатии:
    139
    Прилично, да. Если эти самые элементы не изменяются, то полученный массив лучше записать в файл.
    А если элементы, время от времени меняются, то только перебор.
     
  6. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.501
    Симпатии:
    599
    Я и не предлагаю сохранять.
    Например, если всего два массива, и в каждом два элемента:
    Код (Text):
    1. a, a, b, b
    2. x, z, x, z
    a и b повторяются по два раза подряд. Если генерировать варианты как параллельные массивы, можно использовать array_fill() для быстрого заполнения повторяющися элементов.
    Если три массива, то x, x, z, z будет повторяться дважды, можно использовать array_merge() чтобы приклеивать паттерн столько раз, сколько нужно.
    Если длина элементов известна, то можно все это сделать с помощью параллельных строк, заполняемых паттернами с помощью str_repeat().
     
  7. Drunkenmunky

    Drunkenmunky Новичок

    С нами с:
    12 авг 2020
    Сообщения:
    763
    Симпатии:
    139
    Ключевое слово "если". Я об этом.
    А так-то, да.
    Еще можно такое решить силами sql, но вряд ли быстрей.
     
    #7 Drunkenmunky, 23 фев 2021
    Последнее редактирование: 23 фев 2021
  8. Forward5

    Forward5 Новичок

    С нами с:
    5 фев 2021
    Сообщения:
    11
    Симпатии:
    0
    Входной массив задается пользователем - данные извлекаются из гугл таблиц, где каждый столбец это массив значений.

    По поводу оптимизации, как-то пока не улавливаю.. предлагаете сперва проверять каждый массив на содержание повторяющихся элементов?
     
  9. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.501
    Симпатии:
    599
    Нет, дело не в повторяющихся элементах массива, а в повторах при переборе.
    Честно говоря, не совсем понял с каким массовом работает ваша финальная функция. И какой у неё вывод?
     
  10. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.501
    Симпатии:
    599
  11. Drunkenmunky

    Drunkenmunky Новичок

    С нами с:
    12 авг 2020
    Сообщения:
    763
    Симпатии:
    139
    Интересная мысль, да.
    Но нужно практическое сравнение скорости перебора. На больших массивах.
     
  12. Forward5

    Forward5 Новичок

    С нами с:
    5 фев 2021
    Сообщения:
    11
    Симпатии:
    0
    Да, очень интересное решение, но пока не соображу как его адаптировать для произвольного числа массивов не придя к перебору, чтобы можно было протестировать.. Пример реальных данных:
    [​IMG]

    Число столбцов и длина могут быть произвольные.
    Можно сказать что функционал соответствует веб-сервисам по типу peresekator. ru, только для неограниченного числа списков