All variants of string from array in PHP

Question

I've got a string with spaces. I need to split (explode) it and got all variants of sequences from it. For example:

string1 string2 string3

I need to parse it and get an output like this:

string1 string2 string3
string1 string3 string2
string2 string1 string3
string2 string3 string1
string3 string2 string1
string3 string1 string2

What's the most efficient way to do this?
EDIT: actually i need to parse maximum of 3 strings. So i'm doing this not a pretty way (hardcoded):

$exploded_query = explode(' ', $query);
if(count($exploded_query) == 2) {
//2 variants
}
if(count($exploded_query) == 3) {
//6 variants
}

So i'm looking for some pretty way to do it.

I think you should really be asking whatever question you're trying to answer with this approach. There's no *efficient way* to do this, because you have already stated that you need _every_ combination (the most efficient implementations of certain algorithms will intelligently pick which combinations they need to actually run - and they will short-circuit when possible). This means that the "most efficient" approach to this will still be n! (n factorial). Just 10 words is already 3 million combinations. — Colin M, Apr 09 '13 at 13:02
Take a look at: http://stackoverflow.com/questions/3742506/php-array-combinations — danielrsmith, Apr 09 '13 at 13:13

score 1 · Accepted Answer · answered Apr 09 '13 at 13:36

1

It is a permutation of array

Look here -> Finding All Permutations of an Array, that's help you.

answered Apr 09 '13 at 13:36

cernyjan

36
2

Colin M · Answer 2 · 2013-04-09T13:40:46.937

By no means am I claiming this to be efficient or optimal. There are much better solutions out there. But this is just a direct answer to your question. If you want to remove some bloat (at the cost of likely a little bit of performance), you can replace the getRemainingWords function call with:

$index = 0;
array_values(array_filter($words, function($key, &$index) { return !($key == $index++); }));

Otherwise, here it is

function getPossibleCombinations($words) {
    $combinations = array();
    $count = count($words);

    // Base case: if there's only 1 word, there's only one combination
    if ($count == 1) {
        return array($words);
    }

    // Otherwise, loop over each words
    foreach ($words as $key=>$word) {

        // For each item, get all of the remaining items in the array (all except the current one)
        $otherWords = getRemainingWords($words, $key);

        // And recursively permute them
        $otherCombinations = getPossibleCombinations($otherWords);
        foreach ($otherCombinations as $otherCombination) {
            $combinations[] = array_merge(array($word), $otherCombination);
        }
    }

    return $combinations;
}


function getRemainingWords($array, $index) {
    $results = array();

    foreach ($array as $key=>$value) {
        if ($key == $index) {
            continue;
        }

        $results[] = $value;
    }

    return $results;
}

All variants of string from array in PHP

2 Answers2