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

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.

Nuclear

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"
}
*/

Doormat

Instead of the double foreach, you could also write your own cartesian product function, but it seemed like overkill for this example. – Doormat

This is not a iterative functions. It's recursive, since it clearly keeps calling onto itself... – Pullen

for those who don't want a character to exist more than once in each combination change the last foreach loop to: if (strpos($combination, $char) === false) {$new_combinations[] = $combination . $char;} – Unbridle

Can be performed this function with new version of PHP 7.2 or is there no news to optimize the current function in the new version?@JoelHinz? – Dayak

@AndreasHunter I see no reason why the code wouldn't work in PHP >=7.2, though I'm sure it can be optimised - it was meant as an example of how it works, not as an optimisation. – Doormat

@JoelHinz I am not telling you that your code does not work on newer versions of the language. Your code works on both newer and older versions of the PHP, and I personally tested it. I just wanted to ask whether it is possible to somehow optimize the generation time as using new language features. Thank you for your reply. – Dayak

Don't suppose anyone has any idea to handle this (in terms of memory) for very large string lengths? 4 possible characters at 20 length to be exact. I only need to run it once and store the output. – Byron

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

Godber

Yes that is correct, but how it can be generalized in an algorithm to create combinations of n sizes – Nuclear

@Nuclear That is due to the fact that this property that I described holds for all n. I'll edit. – Godber

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.

Kenaz

I am trying to test it. What is $arra_of_elem and also in the second and third loop use foreach instead of for – Nuclear

@Nuclear It is the array or set where you have the elements to combine. In your case: Array('A', 'B', 'C') – Kenaz

Not working well. For any given size it generates combinations in size 3 – Nuclear

@Nuclear I just tested the code above in writecodeonline.com/php changing the return for a print_r and it works well for combinations of 4 elements – Kenaz

Answer 4

Here is a code made by a friend, it generated unique combinations of X numbers from a list of numbers.

If you have a list of numbers, like 1,3,4,7,12 you can generate sets of X numbers, all unique, no repetitive.

First function works with PHP 7.4 or more, and second uses keys to store the values. Both work very well based on benchmark.

function get_combos74($map, $size, &$generated = [], $loop = 1, $i = 0, $prefix = [])
{
    if ($loop == 1) {
        sort($map);
    }

    for (; $i < count($map); $i++) {
        if ($loop < $size) {
            get_combos74($map, $size, $generated, $loop + 1, $i + 1, [...$prefix, $map[$i]]);
        } else {
            $generated[] = [...$prefix, $map[$i]];
        }
    }

    return $generated;
}
function get_combosSTR($map, $size, &$generated = [], $loop = 1, $i = 0, $prefix = '')
{
    if ($loop == 1) {
        sort($map);
    }

    for (; $i < count($map); $i++) {
        if ($loop < $size) {
            get_combosSTR($map, $size, $generated, $loop + 1, $i + 1, "$prefix{$map[$i]}:");
        } else {
            $generated["$prefix{$map[$i]}"] = 0;
        }
    }

    return $generated;
}

Sentimentality

Answer 5

Another idea using numeric base conversion

$items = ['a', 'b', 'c', 'd'];
$length = 3;
$numberOfSequences = pow(count($items), $length);
for ($i = 0; $i < $numberOfSequences; $i++) {
    $results[] = array_map(function ($key) use ($items) {
        return $items[base_convert($key, count($items), 10)];
    }, str_split(str_pad(base_convert($i, 10, count($items)), $length, 0, STR_PAD_LEFT)));
}

return $results;

Amoreta

Warning, you should not have more elements in the items array than the base_convert parameters can handle : and that number is 36 – Amoreta