Get ALL possible results from mixing array

Question

I've looked everywhere for this online, but couldn't completely find it. (my PHP and math skills are letting my down for this one...) I have an array containing for example three strings (could also be more!) (for example: "a", "b", "c"). Now I want to make a function which returns ALL possibilities. I looked everywhere and found some nice functions who shifted the array in all possibles ways, but they didn't remove a value one by one. So they had:

abc acb bac bca cab cba

Which is fine, but I need a function that takes it to the next level:

abc acb bac bca cab cba ac ca ab ba bc ba a b c

and this regardeless of how many values (let's say max 10). I've been struggling with this the entire evening, can someone put me out of my misery and solve this riddle for me please? Or give some advice. Thanks

Answer 1

As always, it's much more fun to solve the problem your own way. You can modify your code to fit your special needs much easier then, because you know what you are doing :) See my test script below:

<?

$a = array("a", "b", "c");

function getAll($prefix, $remaining)
{
    echo $prefix."\n";

    if (count($remaining) == 0) return;
    if (count($remaining) == 1)
    {                                                                
        echo $prefix.$remaining[0]."\n";
        return;                                                      
    }                                                                

    for ($i = 0; $i < count($remaining); $i++)                       
    {                                                                
        $t = $remaining;                                             
        unset($t[$i]);                                               
        $t = array_values($t);                                       
        getAll($prefix.$remaining[$i], $t);              
    }                                                                                                       
}                                                        
echo "<pre>\n";                                          
getAll('', $a);                                          
echo "</pre>\n";                                         

?>

I just echo'd the intended output, you could add up a result array instead, but that's your part :)

Output:

[] //empty value is included, but blank lines won't show up here, so I wrote []
a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba

Answer 2

It looks like you're asking for the "power set". the power set includes the empty set, which i wont include.

require_once 'Math/Combinatorics.php';
$set = range('a', 'c');
$permutationSizes = range(1, count($set));
$combinatorics = new Math_Combinatorics;
$result = array();
foreach ($permutationSizes as $permutationSize) {
    $result = array_merge($result, $combinatorics->permutations($set, $permutationSize));
}
print_r($result);

http://pear.php.net/package/Math_Combinatorics

I guess technically this isnt a power set because i'm assuming order matters when comparing sets. anyway...