Эффективный алгоритм PHP для генерации всех комбинаций / перестановок входов

Question

Я пытаюсь вычислить все комбинации набора значений в массиве для количества входов. Похож на этот вопрос:

Алгоритм PHP для генерации всех комбинаций определенного размера из одного набора

Например:

function sampling($chars, $size, $combinations = array()) {

  if (empty($combinations)) {
      $combinations = $chars;
  }

  if ($size == 1) {
      return $combinations;
  }

  $new_combinations = array();

  foreach ($combinations as $combination) {
      foreach ($chars as $char) {
          $new_combinations[] = $combination . $char;
      }
  }
  return sampling($chars, $size - 1, $new_combinations);
}

$chars = array('a', 'b', 'c');
$output = sampling($chars, 2);
echo implode($output,', ');

Выход:

aa, ab, ac, ba, bb, bc, ca, cb, cc

Но проблема в том, когда я увеличиваю этот список, например:

$chars = array('a', 'b', 'c', 'd');
$output = sampling($chars, 12);

Количество перестановок резко возрастает, и PHP не хватает памяти. По всей видимости, решение этой проблемы заключается в использовании генераторов и выдаче результатов на протяжении всего цикла. Единственные примеры генераторов для немного разных наборов задач:

См.: /questions/12516302/perestanovki-vse-vozmozhnyie-naboryi-chisel/12516317#12516317

Любые идеи о том, как использовать генераторы для решения этой проблемы?

Answer 1

Дайте этому шанс:

<?php
$chars = array('a','b','c');
$count = 13;

$generator = genCombinations($chars,$count);
foreach ($generator as $value) {
  // Do something with the value here
  echo $value;
}

function genCombinations($values,$count=0) {
  // Figure out how many combinations are possible:
  $permCount=pow(count($values),$count);

  // Iterate and yield:
  for($i = 0; $i < $permCount; $i++)
    yield getCombination($values, $count, $i);
}

// State-based way of generating combinations:
function getCombination($values, $count, $index) {
  $result=array();
  for($i = 0; $i < $count; $i++) {
    // Figure out where in the array to start from, given the external state and the internal loop state
    $pos = $index % count($values);

    // Append and continue
    $result[] = $values[$pos];
    $index = ($index-$pos)/count($values);;
  }
  return $result;
}

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