Miky Miky - 1 month ago 6
PHP Question

php - get all non repetitive combinations of strings (no matter the order)

php:
Given a list of non repetitive strings, like

$strings=array("asd","qwerty","123");// or more


I'd like to get all non repetitive combinations (no matter the order) like

asd
asd qwerty
asd 123
asd qwerty 123
qwerty
qwerty 123
123


I'm looking for the most efficient algorithm possible and in a single function

Answer

The main idea is that number of combinations (if all strings are different) is n^2 - 1, where n = count of strings. Thus we can use binary representation of i-th combination to build our unique combination.

In code it looks like this:

$someArray = ['abc', 'def', 'foo', 'bar'];
$combinations = pow(2, count($someArray)) - 1;

$result = [];

for ($i = 0; $i < $combinations; $i++) {

    $result[$i] = [];

    for ($j = 0; $j < count($someArray); $j++) {
       // here we check if j-th bit of i is equal to 1
       if (($i >> $j) & 1 == 1) {
           $result[$i][] = $someArray[$j];
       }
    }
}