Как найти всевозможные сочетания из n по k?

Question

[Apxu]

Формула, которая считает количество всевозможных сочетаний https://www.matburo.ru/tvart_sub.php?p=calc_C
Передаем количество элементов (в массиве) и количество в группе (сколько элементов из общего массива будет в одном подмассиве).
Задача такая: передаем количество элементов в массиве 15 штук (уникальных) и количество в группе, например 8, после чего скрипт должен скомбинировать между собой все варианты из общего массива и сформировать подмассивы с количеством элементов, как задано, по 8 штук.

Код

//Вначале на простом
$ar = [1,2,3,4,5];
$group = 3;
/* Результат должен получиться следующий
Array
(
    [0] => [1,2,3],
    [1] => [1,2,4],
    [2] => [1,2,5],
    [3] => [1,3,4],
    [4] => [1,3,5],
    [5] => [1,4,5],
    [6] => [2,3,4],
    [7] => [2,3,5],
    [8] => [2,4,5],
    [9] => [3,4,5]
)

С небольшим набором все кажется просто, но что если мы поменяем входные параметры, см.ниже
*/

//Например есть массив
$ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
$group = 8;
//В результате должен получиться массив с 6435 подмассивов в котором группы по 8 уникальных элементов. В одном подмассиве элементы не могут повторяться.

Answer 1

[Александр Измайлов]

Пример с использованием класса.

class CombinationsCalculator
{
    protected $result;
    protected $combination;

    public function getCombinations($array, $group) {
        $this->result = [];
        $this->combination = [];
        $this->iteration(0, $group, $array, count($array));
        return $this->result;
    }

    protected function iteration($start, $step, $array, $n) {
        if ($step == 0) {
            array_push($this->result,$this->combination);
        }
        else {
            for ($i = $start; $i <= $n - $step; ++$i) {
                array_push($this->combination, $array[$i]);
                $this->iteration($i + 1, $step - 1, $array, $n);
                array_pop($this->combination);
            }
        }
    }
}

$calculator = new CombinationsCalculator();
$result = $calculator->getCombinations([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 8);

Comments

[Apxu]

Благодарю! то что нужно!

Answer 2

[Дмитрий]

function combine($arr, $k) {
   $combs = [];
   $comb = range(0, $k - 1);
   
   while($comb) {
      $combs[] = array_map(function($i) use($arr) {return $arr[$i];}, $comb);
      
      for($i = $k - 1, $max = count($arr) - 1; $i > -1; $i--, $max--) {
         if($comb[$i] < $max) {
            $comb[$i] ++;
            for($j = $i + 1; $j < $k; $j++) {
               $comb[$j] = $comb[$j - 1] + 1;
            }
            break;
         } 
      }
      if($i < 0) $comb = null;
   }
   
   return $combs;
}

print_r(combine([1,2,3,4,5], 3));