still_dreaming_1 still_dreaming_1 - 1 month ago 21
PHP Question

Altered Combinations/Permutations Algorithm in PHP

I'm having a hard time writing a function that that takes an array and returns an array of arrays. I'm not sure if this would be considered combinations, permutations, or something else. The results should be similar to some other permutation and combination algorithms I have seen implemented, but not exactly the same.

Let's say the function signature is is like

function variable_length_permutations_with_duplicates($set_array, $max_subset_length)


Then this code:

$sets = variable_length_permutations_with_duplicates(array('a', 'b'), 2);


should return an array of arrays like this:

[
['a'],
['a','a'],
['a','b'],
['b],
['b','b'],
['b','a'],
]


It does need to work with arrays because the values could be anything, they are not necessarily strings like in that example. The subsets in the return array do not need to appear in any particular order.

Do you know of any PHP functions or classes I could use for this or a reference implementation in another language that I could translate to PHP?

Answer

You could use this code -- I made the function name a bit shorter :) :

function perm($set_array, $max_subset_length, $prefix = []) {
    $result = [$prefix];
    if ($max_subset_length) {
        foreach ($set_array as $el) {
            $result = array_merge($result, 
                perm($set_array, $max_subset_length-1, array_merge($prefix, [$el])));
        }
    }
    return $result;
}

$sets = perm(array('a', 'b'), 2);   

print_r($sets);

Note that in this logic, also the empty array is included in the result. With an if you can exclude this as follows in the first line of the function:

    $result = count($prefix) ? [$prefix] : [];
Comments