@ventacom

Как составить все возможные сочетания из элементов разных массивов размером N?

Добрый день!
Имеется N кол-во массивов разных размеров. Например:
[A, B, C]
[1, 2, 3, 4, 5, 6]
[X, Y, W, Z]
....
[one, two, three]

Необходимо перебрать все возможные комбинации элементов массивов, но чтобы кол-во эл-тов в получившемся одномерном массиве не было больше 2/ 3 (сколько укажешь). При этом из каждого массива берется только 1 значение
Так, при лимите 2 может получиться:
[A, 1]
[A, two]
[C, W]
...
при лимите в 3 эл-та:
[1, Z, three]
[C, 5, W]
...
то есть не нужно, чтобы все N массивов участвовали в образовании сочетаний.
Помогите составить рекурсию на php, чтобы собрать все возможные сочетания элементов массиовов, при условии что в каждом массиве свое кол-во эл-то и само кол-во массивов тоже может меняться
  • Вопрос задан
  • 276 просмотров
Пригласить эксперта
Ответы на вопрос 4
vechnokrainii
@vechnokrainii
ну почти всегда(
Не знаю насчет рекурсии, но можно сделать проще
Загоняешь все в один двумерный массив, то есть делаешь матрицу
У умножаешь кол-во элементов каждой строки друг на друга.
Т.е. к примеру у тебя три массива в одном 5 в другом 4 и в третьем 6 эдементов. получается все комбинации будут = 5*4*6 + 4*6 = 144 пары. Хотя наверняка есть формула в математике готовая. Попробуй почитай в комбинаторике
Ответ написан
@Fomichevap
$array1 = [a,1];
$array2 = [A,two];
$array3 = [C,W];
$arrToMerge = [0=>$array1,1=>$array[2],2=>$array3];
$result_array = [];
$length = 3; #длина которая нужна

for ($i = 0; $i < $length; $i++) {
$arrCur = rand(0,sizeof($arrToMerge)); #рандомный массив
$arrElCur = rand(0,sizeof($arrToMerge[$arrCur]));
$result_array[] = $arrToMerge[$arrCur][$arrElCur];
//in_array($arrToMerge[$arrCur][$arrElCur],$result_array) ? null : $result_array[] = $arrToMerge[$arrCur][$arrElCur];#Или так, если нужны уникальные
}


print_r($result_array);
Ответ написан
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Во первых, загоните входные данные в двумерный массив, или список массивов или что там вообще в php есть, чтобы можно было взять первый, второй и т.д. входной массив по номеру или перейти к следующему.

Далее, как вы уже знаете, нужна рекурсивная функция. Передаевайте ей уже собранную часть ответа и какой из массивов надо использовать следующим (итератор в списке или номер в массиве).

Функция берет из текущего массива один из элементов в цикле и добавляет его к ответу и запускается рукурсивно от следующего массива. Еще функция не берет ничего из текущего массива и запускается рекурсивно.

Надо вставить следующие проверки: Если функция запущена от после-последнего массива, то надо вывести текущий ответ. Цикл по элементам текущего массива пропускается, если в ответе уже максимально возможное количество элементов.
Рекурсивный вызов без добавления элемента пропускается, если оставшихся дальше массивов столько же, сколько не хватает элементов в текущем ответе до минимально нужного размера.

Псевдокод примерно такой (не php, чтобы не позориться):

function Generate(result, array_index, arrays) {
  if(result >= len(arrays)) {
    print(result)
    return
  }
  if (min_length - len(result) < len(arrays)-array_index-1) {
    Generate(answer, array_index+1, arrays);
  }
  if (len(answer) < max_length) {
    for i = 0...len(arrays[array_index]) {
      answer.push_back(arrays[array_index][i]);
      Generate(answer, array_index+1, arrays);
      answer.pop_back();
    }
  }
}
Ответ написан
составить универсальный код сходу не получилось. Думаю, надо составлять код динамически, через create_function().
Для случая двух элементов вот код:
$sources = [
    ['A', 'B', 'C',],
    [1, 2, 3, 4, 5, 6,],
    ['X', 'Y', 'W', 'Z'],
    ['1X', '2Y', '3W', '4Z'],
];
function combine_by_two( $source ) {
    $result = [];
    // нужно, чтобы было хотя бы 2 массива-источника
    while ( count($source) > 1 ) {
        /**
         * AFAIK, технически легче оперировать с последним элементом, а не первым
         * (что привычнее для человека)
         */
        $primary = array_pop($source);
        $linearizedArray = call_user_func_array("array_merge", $source);
        foreach ($primary as $primaryItem) {
            foreach ($linearizedArray as $secondaryItem) {
                $result[] = [$primaryItem, $secondaryItem];
            }
        }
        // повторяем с усечённым массивом
        $result += combine_by_two($source);
    }
    return $result;
}

$combined = combine_by_two($sources);
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Laptop.ru Москва
от 150 000 до 190 000 ₽
DKLINE Санкт-Петербург
от 120 000 до 150 000 ₽
Laptop.ru Москва
от 130 000 до 170 000 ₽
18 июн. 2021, в 09:44
3000 руб./за проект
18 июн. 2021, в 09:33
1000 руб./в час
18 июн. 2021, в 09:30
1800 руб./за проект