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?

Off the cuff, I would say do some sort of pagination-type logic. use a $_GET variable for the length and starting number, then only display those to the screen, and display more on another page load.. — Stevish, Apr 14 '16 at 02:07
1) Do you want to get the combinations now or permutation? 2) You pass `12` as length, but get `aa` as a result?! 3) What is the expected output with `[a, b, c]` and length `3` ? — Rizier123, Apr 14 '16 at 05:01
`[a,b,c]` length `12` would be would be: `aaaaaaaaaaaa, aaaaaaaaaab, aaaaaaaaaac. I hope that helps! — Luc, Apr 14 '16 at 05:03
@Luc And `aab` and `baa` would be something different? If yes you want the permutation, not only the combinations. — Rizier123, Apr 14 '16 at 05:05
@Rizier123, sorry, some formatting issues there. Yeah, that's right, I want all combinations from the input array for a range of lengths. — Luc, Apr 14 '16 at 05:06
@Rizier123 I just need all combinations, so no, `aab` and `baa` would be needed. All possible combinations need to be considered — Luc, Apr 14 '16 at 05:16
@Rizier123 so I should have avoided using the word 'permutation'... as I see where you are coming from. I'm just after all samples/combinations for a solution here... A solution that doesn't kill my memory. — Luc, Apr 14 '16 at 05:18
@Luc No, if you want both `aab` AND `baa`, this would mean the order is important and the two would be different, and that would be called permutation where the order makes a difference. While for combinations the order wouldn't make a difference, so `aab`, `aba` and `baa` would be all the same combination, but 3 different permutations. — Rizier123, Apr 14 '16 at 05:22

score 6 · Accepted Answer · edited Apr 14 '16 at 05:31

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.

1) To output the results change: `echo $value;` to `echo implode(",", $value) . "
";` 2) Since the order is important this would be called permutation: https://en.wikipedia.org/wiki/Permutation — Rizier123, Apr 14 '16 at 05:38

Efficient PHP algorithm to generate all combinations / permutations of inputs

1 Answers1

Linked