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
– Stevish, Commented Apr 14, 2016 at 2: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
– Rizier123, Commented Apr 14, 2016 at 5:01
[a,b,c] length 12 would be would be: `aaaaaaaaaaaa, aaaaaaaaaab, aaaaaaaaaac. I hope that helps! — Luc
– Luc, Commented Apr 14, 2016 at 5:03
@Luc And aab and baa would be something different? If yes you want the permutation, not only the combinations. — Rizier123
– Rizier123, Commented Apr 14, 2016 at 5: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
– Luc, Commented Apr 14, 2016 at 5:06

GAMITG · Accepted Answer · 2016-04-14 05:31:19Z

6

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.

edited Apr 14, 2016 at 5:31

GAMITG

3,8187 gold badges35 silver badges51 bronze badges

answered Apr 14, 2016 at 5:28

jimmyd_au

762 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Rizier123 Over a year ago

1) To output the results change: echo $value; to echo implode(",", $value) . "<br />"; 2) Since the order is important this would be called permutation: en.wikipedia.org/wiki/Permutation

Collectives™ on Stack Overflow

Efficient PHP algorithm to generate all combinations / permutations of inputs

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related