PHP Arrays and Recursive Iterations

Question

I have a scenario that I think requires some kind of recursive iterations, but I am not certain, and not being an expert on recursive coding, I am drawing a blank.

Here is the scenario:

I have a phrase something like this:

[He|She] would [like|love|hate] to [Play Golf|Play Tennis|Play Baseball] Today.

I would like PHP to parse through that phrase (each section inside [] brackets represents possible variations for that word or phrase, each possibility separated by a | pipe), and generate all variations, so for example, the above would return:

He would like to Play Golf Today. 
He would like to Play Tennis Today.
He would like to Play Baseball Today.
He would love to Play Golf Today.
He would love to Play Tennis Today.
He would love to Play Baseball Today.
He would hate to Play Golf Today.
He would hate to Play Tennis Today.
He would hate to Play Baseball Today.
She would like to Play Golf Today.
She would like to Play Tennis Today.
She would like to Play Baseball Today.
She would love to Play Golf Today.
She would love to Play Tennis Today.
She would love to Play Baseball Today.
She would hate to Play Golf Today.
She would hate to Play Tennis Today.
She would hate to Play Baseball Today.

I am trying to figure out how to write PHP code to take the inputted phrase, and return all possible sentences.

finite state machine to parse the phrase and generate all the sentences? — user4035, Jul 27 '13 at 20:38
For my purposes, I guess we can put a limit of 10 possible items per [] group, and 10 total 'pieces' to the sentence (each piece can be a singular value, or a [] group). Does that answer? — OneNerd, Jul 27 '13 at 20:41
I think, it's possible to do for arbitrary number of items per group — user4035, Jul 27 '13 at 20:42
What you want to do is find the cartesian product of the possible inputs, after which it is trivial to generate the output you want with a simple `foreach`. There are several good ways to do this (including an answer of my own) here: http://stackoverflow.com/questions/6311779/finding-cartesian-product-with-php-associative-arrays. If you need more guidance on how to do this I can expand into an answer. — Jon, Jul 27 '13 at 22:43

user4035 · Accepted Answer · 2013-07-28T05:58:45.833

Here is a recursive solution:

<?php
function generator($input, &$result)
{
    $matches = array();
    if (preg_match('/\[(.*?)\]/', $input, $matches))
    {
        $words = explode('|', $matches[1]);
        $n = count($words);
        for ($i = 0; $i < $n; ++$i)
        {
            $input1 = str_replace($matches[0], $words[$i], $input);
            generator($input1, $result);
        }
    }
    else
    {
        $result[] = $input;
    }
}

$input = '[He|She] would [like|love|hate]';
$result = array();
generator($input, $result);
var_dump($result);

Prints 2*3 = 6 combinations:

array(6) {
  [0]=>
  string(13) "He would like"
  [1]=>
  string(13) "He would love"
  [2]=>
  string(13) "He would hate"
  [3]=>
  string(14) "She would like"
  [4]=>
  string(14) "She would love"
  [5]=>
  string(14) "She would hate"
}

I wanted to use yeild, but my php version (5.4.7) is too old for it.

Thanks! This is exactly what I was looking for (especially the generator() function)! — OneNerd, Jul 28 '13 at 04:43
@OneNerd After I got up from sleep, I realized, how to improve the function. Take a look: I got rid of is_null check. — user4035, Jul 28 '13 at 06:00

score 0 · Answer 2 · answered Jul 27 '13 at 22:15

First of all you have to split the input string and rewrite it as an array. This will have an output like this: (I would use strpos, regexp and/or explode to split all parts)

Array(
    [0]=> Array(
        [0] => 'He',
        [1] => 'She'),
    [1]=> Array(
        [0] => ' would '),
    [2]=> Array(
        [0] => 'like',
        [1] => 'love',
        [2] => 'hate'),
...
)

After you have to loop through the array and build all combinations and store them into strings. This will look like this

//this is for tracking the progress
for($x = 0; $x < count($array_parts); $x++)
{
    //starting all at the first option
    $array_tracker[$x] = 0;
}

while(true)
{
    //build selected possibility
    $ouput_string = "";
    for($x = 0; $x < count($array_parts); $x++)
    {
        $ouput_string .= $array_parts[$x][$array_tracker[$x]];
    }
    $output_strings[] = $output_string;

    //navigate to next possibility
    for($x = count($array_parts) - 1; $x >= 0; $x--)
    {
        $array_tracker[$x]++;
        if($array_tracker[$x] == count($array_parts[$x))
        {
            $array_tracker[$x] = 0;
        }
        else
        {
            break;
        }
        if($x == 0)
        {
            //all option are done, than end this 'endless' loop
            break 2;
        }
    }
}

score 0 · Answer 3 · 2013-07-28T00:39:30.410

$string = '[He|She] would [like|love|hate] to [Play Golf|Play Tennis|Play Baseball] Today.';
$parts = explode("]", $string);
$newparts = array();
$loops = array();
foreach($parts as $part){
 if(strpos($part, '[') !== false){
    $part = preg_replace("#([^\[]+)?\[#", "", $part);
    $loops[] = explode("|", $part);
 }
}
//matching other words

$words = preg_replace("#\[(.*?)\]#", '', $string);
$words = preg_replace("#\s+#", '|', trim($words));
$words = explode("|", $words);

foreach($loops as $key => &$val){

    foreach($val as &$word){
      $word = $word.' '.$words[$key];
    }
}
$data =array();

$eval = '
 $data =array();
 ';
$eval_blocks = '';
$eval_foreach = '';
$eval_data = '
$data[] = ';
$looplength = count($loops);
for($i=0; $i<$looplength; $i++){
 $eval_foreach.= '
 foreach($loops['.$i.'] as $val'.($i+1).'){
 ';
 if( ($i+1) == $looplength ){
  $eval_data .= ' $val'.($i+1).';';
 }else{
  $eval_data .= ' $val'.($i+1).' ." ".';
 }
 $eval_blocks .= '
 }
 ';
}
$eval = $eval. $eval_foreach . $eval_data . $eval_blocks;
echo "<hr>";
print_r($words);
print_r($loops);
print_r($data);

Output:

Array
(
    [0] => would
    [1] => to
    [2] => Today.
)
Array
(
    [0] => Array
        (
            [0] => He would
            [1] => She would
        )

    [1] => Array
        (
            [0] => like to
            [1] => love to
            [2] => hate to
        )

    [2] => Array
        (
            [0] => Play Golf Today.
            [1] => Play Tennis Today.
            [2] => Play Baseball Today.
        )

)
Array
(
    [0] => He would like to Play Golf Today.
    [1] => He would like to Play Tennis Today.
    [2] => He would like to Play Baseball Today.
    [3] => He would love to Play Golf Today.
    [4] => He would love to Play Tennis Today.
    [5] => He would love to Play Baseball Today.
    [6] => He would hate to Play Golf Today.
    [7] => He would hate to Play Tennis Today.
    [8] => He would hate to Play Baseball Today.
    [9] => She would like to Play Golf Today.
    [10] => She would like to Play Tennis Today.
    [11] => She would like to Play Baseball Today.
    [12] => She would love to Play Golf Today.
    [13] => She would love to Play Tennis Today.
    [14] => She would love to Play Baseball Today.
    [15] => She would hate to Play Golf Today.
    [16] => She would hate to Play Tennis Today.
    [17] => She would hate to Play Baseball Today.
)

Update: the loop dynamically created.

DEMO: http://codepad.org/eeQd9S0r

Expedito · Answer 4 · 2013-07-28T07:53:52.807

Recursive function for generating the combinations:

function combix($items, $combos=array()){
    $res = array();
    $next = array_shift($items);
    if (is_array($next)){
        if (empty($combos)){
            return combix($items, $next);
        }
        foreach ($combos as $key => $value){
            foreach ($next as $key2 => $value2){
                if (is_array($value)){
                    $res[] = array_merge($value, array($value2));
                } else {
                    $res[] = array($value, $value2);
                }
            }
        }
        return combix($items, $res);
    } else {
        return $combos;
    }
}

Text processing:

$str = '[He|She] would [like|love|hate] to [Play Golf|Play Tennis|Play Baseball] Today.';
$pattern = '#\[([\w\s|]+)]#';
if (preg_match_all($pattern, $str, $matches)){
    $template = preg_replace($pattern, '%s', $str);
    $mix = array();
    foreach ($matches[1] as $key => $value){
        $mix[] = explode('|', $value);
    }
    $res = combix($mix);
    $out = array();
    foreach ($res as $key => $value){
        array_unshift($value, $template);
        $out[] = call_user_func_array('sprintf', $value);
    }
} else {
    $out = array($str);
}
print_r($out);

Any way (using your code) to account for more or less that 3 [] bracketed work groups in the string? — OneNerd, Jul 28 '13 at 04:08

PHP Arrays and Recursive Iterations

4 Answers4