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

I think this is what you're looking for: http://stackoverflow.com/questions/2617055/how-to-generate-all-permutations-of-a-string-in-php — , May 20 '12 at 21:28
@AustinAllover, the linked question is different in that it asks for permutations of size n, not of all sizes. — goat, May 20 '12 at 21:39

score 1 · Answer 1 · answered May 20 '12 at 21:31

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...

score 1 · Accepted Answer · answered May 21 '12 at 05:53

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

score 0 · Answer 3 · answered May 20 '12 at 21:54

There's an example function for permutations on O'Reilly's PHP Cookbook, section 4.26. It only creates permutations of a fixed size, but can be used in a loop to deal with any size like you need it.

Code

function pc_next_permutation($p, $size) {
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
         $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }
    return $p;
}

$set = explode(' ', 'a b c');

// $all will contain the final output
$all = $set;
while(count($set) > 1) {
    $perms = array();
    $size = count($set) - 1;
    $perm = range(0, $size);
    $j = 0;

    do { 
         foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
    } while ($perm = pc_next_permutation($perm, $size) and ++$j);

    foreach ($perms as $p) {
         $all[] = implode(' ', $p);
    }
    array_pop($set);    
}

// display results
foreach($all as $each) {
    echo $each . "\n";
}

Output

a
b
c
a b c
a c b
b a c
b c a
c a b
c b a
a b
b a

Live example

Get ALL possible results from mixing array

3 Answers3

Code

Output

Linked

Related