"Unfolding" a String

Question

I have a set of strings, each string has a variable number of segments separated by pipes (|), e.g.:

$string = 'abc|b|ac';

Each segment with more than one char should be expanded into all the possible one char combinations, for 3 segments the following "algorithm" works wonderfully:

$result = array();
$string = explode('|', 'abc|b|ac');

foreach (str_split($string[0]) as $i)
{
    foreach (str_split($string[1]) as $j)
    {
        foreach (str_split($string[2]) as $k)
        {
            $result[] = implode('|', array($i, $j, $k)); // more...
        }
    }
}

print_r($result);

Output:

$result = array('a|b|a', 'a|b|c', 'b|b|a', 'b|b|c', 'c|b|a', 'c|b|c');

Obviously, for more than 3 segments the code starts to get extremely messy, since I need to add (and check) more and more inner loops. I tried coming up with a dynamic solution but I can't figure out how to generate the correct combination for all the segments (individually and as a whole). I also looked at some combinatorics source code but I'm unable to combine the different combinations of my segments.

I appreciate if anyone can point me in the right direction.

Answer 1

Recursion to the rescue (you might need to tweak a bit to cover edge cases, but it works):

function explodinator($str) {
    $segments = explode('|', $str);
    $pieces = array_map('str_split', $segments);

    return e_helper($pieces);
}

function e_helper($pieces) {

    if (count($pieces) == 1)
        return $pieces[0];

    $first = array_shift($pieces);
    $subs = e_helper($pieces);

    foreach($first as $char) {
        foreach ($subs as $sub) {
            $result[] = $char . '|' . $sub;
        }
    }

    return $result;
}

print_r(explodinator('abc|b|ac'));

Outputs:

Array
(
    [0] => a|b|a
    [1] => a|b|c
    [2] => b|b|a
    [3] => b|b|c
    [4] => c|b|a
    [5] => c|b|c
)

As seen on ideone.

Answer 2

This looks like a job for recursive programming! :P I first looked at this and thought it was going to be a on-liner (and probably is in perl). There are other non-recursive ways (enumerate all combinations of indexes into segments then loop through, for example) but I think this is more interesting, and probably 'better'.

 $str = explode('|', 'abc|b|ac');
 $strlen = count( $str );
 $results = array();

 function splitAndForeach( $bchar , $oldindex, $tempthread) {
     global $strlen, $str, $results;
     $temp = $tempthread;
     $newindex = $oldindex + 1;

     if ( $bchar != '') { array_push($temp, $bchar ); }

     if ( $newindex <= $strlen ){
         print "starting foreach loop on string '".$str[$newindex-1]."' \n";

         foreach(str_split( $str[$newindex - 1] ) as $c) {
             print "Going into next depth ($newindex) of recursion on char $c \n";
             splitAndForeach( $c , $newindex, $temp);
         }

     } else {

        $found = implode('|', $temp);
        print "Array length (max recursion depth) reached, result: $found \n";

        array_push( $results, $found );
        $temp = $tempthread;
        $index = 0;
        print "***************** Reset index to 0 *****************\n\n";
     }
 }

 splitAndForeach('', 0, array() );
 print "your results: \n";
 print_r($results);