Как получить все комбинации элементов массива размером не менее и не более К елементов?

Question

[sobwoofer]

Есть одномерный отсортированный по возрастанию массив натуральных чисел, содержащий N элементов. И натуральное число K.
Нужно создать алгоритм (скрипт на php), он должен выдавать многомерный массив, который состоит из массивов, содержащих все комбинации элементов входящего массива и имеет размер К. При этом каждый такой массив должен остаться отсортированным по возрастанию.

Пример:
Входящий массив [1, 2, 3, 4]
K = 3
—
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

Comments

[Елнур Уразымбетов]

Использовать цикл и рекурсивную функцию?

Answer 1

[Елнур Уразымбетов]

Для тренировки мозга попробовали сделать вот так:

function process($input, $k, array $prefix = array())
{
    $result = [];

    if ( $k === 1 )
    {
        foreach ($input as $item)
        {
            $result[] = array_merge($prefix, [$item]);
        }
    }
    else
    {
        $n = count($input);
        $m = $n - $k + 1;

        for ( $i = 1; $i <= $m; $i++ )
        {
            $subInput = array_slice($input, $i, $k);
            $subPrefix = array_merge($prefix, [$input[$i-1]]);
            $r = process($subInput, $k-1, $subPrefix);
            $result = array_merge($result, $r);
        }
    }

    return $result;
}


$input = [1, 2, 3, 4, 5];
$k = 3;
$result = process($input, $k);
var_export($result);

Comments

[Araik]

Этот алгоритм выводит не все возможные варианты комбинаций.