Efficient PHP algorithm to generate all combinations / permutations of inputs

Question

I'm trying to calculate all combinations of an set of values in an array for a number of inputs. Similar to this Question:

PHP algorithm to generate all combinations of a specific size from a single set

For example:

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,', ');

Output:

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

But the trouble is when I ramp this up to a larger list, for example:

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

The number of permutations dramatically increases and PHP runs out of memory. Apparently the solution to this is to use generators and yield the results throughout the looping. The only examples of generators though are for slightly different problem sets:

See: https://stackoverflow.com/a/27160465/345086

Any ideas on how to use generators to solve this problem?

Answer 1

Give this a shot:

<?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;
}

It is a state-based fixed-length combination generator that should hopefully fit the bill. It will only accept arrays and will return combinations of the array items, regardless of what is actually stored in the array.