PHP algorithm to generate all combinations of a sp

Question

I am trying to deduce an algorithm which generates all possible combinations of a specific size something like a function which accepts an array of chars and size as its parameter and return an array of combinations.

Example: Let say we have a set of chars: Set A = {A,B,C}

a) All possible combinations of size 2: (3^2 = 9)

AA, AB, AC
BA, BB, BC
CA, CB, CC

b) All possible combinations of size 3: (3^3 = 27)

AAA, AAB, AAC,
ABA, ABB, ACC,
CAA, BAA, BAC,
.... ad so on total combinations = 27

Please note that the pair size can be greater than total size of pouplation. Ex. if set contains 3 characters then we can also create combination of size 4.

EDIT: Also note that this is different from permutation. In permutation we cannot have repeating characters for example AA cannot come if we use permutation algorithm. In statistics it is known as sampling.

Answer 1

I would use a recursive function. Here's a (working) example with comments. Hope this works for you!

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

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);

}

// example
$chars = array('a', 'b', 'c');
$output = sampling($chars, 2);
var_dump($output);
/*
array(9) {
  [0]=>
  string(2) "aa"
  [1]=>
  string(2) "ab"
  [2]=>
  string(2) "ac"
  [3]=>
  string(2) "ba"
  [4]=>
  string(2) "bb"
  [5]=>
  string(2) "bc"
  [6]=>
  string(2) "ca"
  [7]=>
  string(2) "cb"
  [8]=>
  string(2) "cc"
}
*/

Answer 2

You can do this recursively. Note that as per your definition, the "combinations" of length n+1 can be generated from the combinations of length n by taking each combination of length n and appending one of the letters from your set. If you care you can prove this by mathematical induction.

So for example with a set of {A,B,C} the combinations of length 1 are:

A, B, C

The combinations of length 2 are therefore

(A, B, C) + A = AA, BA, CA
(A, B, C) + B = AB, BB, BC
(A, B, C) + C = AC, CB, CC

This would be the code and here on ideone

function comb ($n, $elems) {
    if ($n > 0) {
      $tmp_set = array();
      $res = comb($n-1, $elems);
      foreach ($res as $ce) {
          foreach ($elems as $e) {
             array_push($tmp_set, $ce . $e);
          }
       }
       return $tmp_set;
    }
    else {
        return array('');
    }
}
$elems = array('A','B','C');
$v = comb(4, $elems);

Answer 3

A possible algorithm would be:

$array_elems_to_combine = array('A', 'B', 'C');
$size = 4;
$current_set = array('');

for ($i = 0; $i < $size; $i++) {
    $tmp_set = array();
    foreach ($current_set as $curr_elem) {
        foreach ($array_elems_to_combine as $new_elem) {
            $tmp_set[] = $curr_elem . $new_elem;
        }
    }
    $current_set = $tmp_set;
}

return $current_set;

Basically, what you will do is take each element of the current set and append all the elements of the element array.

In the first step: you will have as result ('a', 'b', 'c'), after the seconds step: ('aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc') and so on.