I have written a function for you here:

<?php

function permutations($array)
{
 $list = array();
 for ($i=0; $i<=10000; $i++) {
  shuffle($array);
  $tmp = implode(',',$array);
  if (isset($list[$tmp])) {
   $list[$tmp]++;
  } else {
   $list[$tmp] = 1;
  }
 }
 ksort($list);
 $list = array_keys($list);
 return $list;
}



function CreateRegex($array)
{
    $toReturn = '/';
    foreach($array AS $value)
    {
        //Contains spaces
        if(strpos($value, " ") != false)
        {
            $pieces = explode(" ", $value);
            $combos = permutations($pieces);
            foreach($combos AS $currentCombo)
            {
                $currentPieces = explode(',', $currentCombo);
                foreach($currentPieces AS $finallyGotIt)
                {
                    $toReturn .= '\b' . $finallyGotIt . '.*?';
                }
                $toReturn = substr($toReturn, 0, -3) . '|';
            }
        }
        else
        {
            $toReturn .= '\b' . $value . '|';
        }
    }

    $toReturn = substr($toReturn, 0, -1) . '/';
    return $toReturn;
}




var_dump(CreateRegex(array('apple', 'banana', 'strawberry', 'pear cake')));

?>

I got the permutations function from:

http://www.hashbangcode.com/blog/getting-all-permutations-array-php-74.html

But I would recommend to find a better function and use another one since just at first glance this one is pretty ugly since it increments $i to 10,000 no matter what.

Also, here is a codepad for the code:

http://codepad.org/nUhFwKz1

Let me know if there is something wrong with it!

Did you take a look at the Hoa\Regex library? It generates strings based on regular expression with an isotropic random approach.