1

Is there any way to get permutation of all words in a string using only regular expression in php.

For example:

for input like "How to remove pain in human knee"

I want output as:

"How To", "How","pain knee","remove knee","knee pain","in remove","human pain knee", etc.

Ankit Agarwal
  • 1,350
  • 10
  • 15
  • So what you want is the powerset of the words of the string right? You may adapt this [answer](http://stackoverflow.com/questions/6092781/finding-the-subsets-of-an-array-in-php) – Richard May 03 '16 at 07:21
  • i want only regular expression – Ankit Agarwal May 03 '16 at 07:22
  • 3
    Oh right, I skipped that part of the question sorry. Well regular expression are meant to match elements of strings, not to build a set. You can use regex to split your string, but ultimately, you will need more code to achieve your goal. – Richard May 03 '16 at 07:26
  • It can't be done only with regular expression – kamal pal May 03 '16 at 07:34

1 Answers1

0

Using regex will only serve to slow down the process.

I have written a function based on the powerSet() function posted by Yada @ https://stackoverflow.com/a/27968556/2943403)

Code: (Demo)

function permStacker($array){
    $stack=[[]];  // declare intitial empty element
    foreach($array as $element){
        foreach($stack as $combination){
            foreach(array_diff($array,$combination) as $left){
                $merge=array_merge($combination,[$left]);
                $stack[implode(' ',$merge)]=$merge;  // keys hold desired strings, values hold subarray of combinations for iterated referencing
            }
        }
    }
    unset($stack[0]); // remove initial empty element
    return array_keys($stack);  // return array of permutations as space delimited strings
}

$string='How to remove pain in human knee';
$permutations=permStacker(explode(' ',$string));
echo 'Total Permutations: ',sizeof($permutations),"\n";
var_export($permutations);

Output:

Total Permutations: 13699
array (
  0 => 'How',
  1 => 'to',
  2 => 'remove',
  3 => 'pain',
  4 => 'in',
  5 => 'human',
  6 => 'knee',
  7 => 'How to',
  8 => 'How remove',
  9 => 'How pain',
  10 => 'How in',
  11 => 'How human',
  12 => 'How knee',
  13 => 'to How',
  14 => 'to remove',
  15 => 'to pain',
  16 => 'to in',
  17 => 'to human',
  18 => 'to knee',
  19 => 'remove How',
  20 => 'remove to',
  21 => 'remove pain',
  22 => 'remove in',
  23 => 'remove human',
  24 => 'remove knee',
  25 => 'pain How',
  26 => 'pain to',
  27 => 'pain remove',
  28 => 'pain in',
  29 => 'pain human',
  30 => 'pain knee',
  31 => 'in How',
  32 => 'in to',
  33 => 'in remove',
  34 => 'in pain',
  35 => 'in human',
  36 => 'in knee',
  37 => 'human How',
  38 => 'human to',
  39 => 'human remove',
  40 => 'human pain',
  41 => 'human in',
  42 => 'human knee',
  43 => 'knee How',
  44 => 'knee to',
  45 => 'knee remove',
  46 => 'knee pain',
  47 => 'knee in',
  48 => 'knee human',
  49 => 'How to remove',
  50 => 'How to pain',
  51 => 'How to in',

Here is a post by bob at math.stackexchange which confirms that 13699 is the expected size of the returned array when given 7 words in the input string. Furthermore, bob's breakdown should serve as a warning about how the permutations ramp up rather fast -- be careful with your big strings.

mickmackusa
  • 43,625
  • 12
  • 83
  • 136
  • @AnkitAgarwal It is necessary that I inform you that my previous method was incorrect. If you were using it in one of our projects, please replace the function immediately as it was given false results. My new method proves to be correct now. Sorry for my mistake. – mickmackusa Nov 08 '17 at 13:44