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

Question

[ventacom]

Добрый день!
Имеется 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, чтобы собрать все возможные сочетания элементов массиовов, при условии что в каждом массиве свое кол-во эл-то и само кол-во массивов тоже может меняться

Answer 1

[Вечно Крайний]

Не знаю насчет рекурсии, но можно сделать проще
Загоняешь все в один двумерный массив, то есть делаешь матрицу
У умножаешь кол-во элементов каждой строки друг на друга.
Т.е. к примеру у тебя три массива в одном 5 в другом 4 и в третьем 6 эдементов. получается все комбинации будут = 5*4*6 + 4*6 = 144 пары. Хотя наверняка есть формула в математике готовая. Попробуй почитай в комбинаторике

Comments

[Вечно Крайний]

Точнее умножаешь сверху вниз. Первый строку на все снизу, втроую тоже на все снизу и так далее. А потом складываешь. В цикл засунешь и норм

[Михаил Ливач]

Насколько я понял условие, у автора строго задаётся количество элементов в сочетании. Поэтому Ваш расчёт неверен: если на входе массивы в 5 элементов, 4 элемента, 6 элементов, то
для случая "два элемента" будет:
5*(4+6)+4*6 = 74 сочетания
для случая "3 элемента" будет:
5*4*6 = 120 сочетаний.

P.S. на всякий случай проверил определение сочетания - порядок элементов неважен. То есть [1, 'A'] эквивалентно ['A', 1]

[Вечно Крайний]

Михаил Ливач, да я немного не так написал. Однако если судить по тому, что я написал. То имел я ввиду то что посчитали вы)

Answer 2

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

Comments

[Вечно Крайний]

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

Answer 3

[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();
    }
  }
}

Answer 4

[Михаил Ливач]

составить универсальный код сходу не получилось. Думаю, надо составлять код динамически, через 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);

Comments

[Михаил Ливач]

есть простой неэффективный алгоритм для для любой длины набора элементов ("кортежа"):
1) сливаем все исходные массивы в одну кучу;
2) из этой кучи составляем все возможные сочетания нужной длины;
3) проходимся по результату и для каждого кортежа считаем array_intersect() с каждым исходным массивом. Если размер результата больше единицы - такой кортеж выбрасываем.

[Вечно Крайний]

Михаил Ливач, это подойдет только в том случае, если все элементы уникальны