generating permutations and combinations...

[henryrhenryr]

Hi

here's a test of logic for mathmeticians (I do have an actual use for this too...)

I need to split a 4 or 5 word phrase into all possible combinations of the individual words:

eg:

4
Post your question in
3
Post your question
post question in
post your in
your question in
2
post your
post question
post in
your question
your in
question in
1
post
your
question
in


It is a matter of logic but I wondered if anyone's already solved it before I spend another 2 hours working it out...

Thanks in advance!

Henry

[ronverdonk]

This is a PHP programming forum, not a logic puzzle solving forum. So show the PHP code you have done so far to get to the solution. And put it between coding tags.

Ronald

[henryrhenryr]

I'm not sure about the difference between programming and logic? Maybe you can enlighten me?

In the meantime, I have been working on it for the past 90 mins and coming to this.

$phrase="A B C D E";
$words=explode(' ',$phrase);
$c=count($words);
$out=array();
for ($i=1;$i<=$c;$i++) {
  if ($i==1) {
    foreach ($words as $w) { 
      $out[$i][]=$w; 
    }
  }
  if ($i==2) {
    for ($j=0;$j<$c;$j++) {
      $next=$j+1;
      if ($next>=$c) {
        $next=$next-$c;
      }
      $out[$i][]= "{$words[$j]} {$words[$next]}";
    }
    if (($c-$i)>1) {
      for ($j=0;$j<$c;$j++) {
        $next=$j+2;
        if ($next>=$c) {
          $next=$next-$c;;
        }
        $out[$i][]= "{$words[$j]} {$words[$next]}";
      }
    }
  }
}
 

[henryrhenryr]

Yup...took exactly 2 hours...

Could be nicer. Works for up to 5 words. Works for more but then starts to miss some combinations. The sequence is like pascal's triangle if anyone's interested. Maybe there's a logical programming forum where such problems are welcome?

$phrase="A B C D E";
$words=explode(' ',$phrase);
$c=count($words);
$out=array();
for ($i=1;$i<$c;$i++) {
  if ($i==1) {
    foreach ($words as $w) {
      $out[$i][]=$w; 
    }
  }
  else {
    for ($j=0;$j<$c;$j++) {
      $z=array();
      for ($k=1;$k<=$i;$k++) {
        $z[$k]=$j+$k-1;
        if ($z[$k]>=$c) {
          $z[$k]-=$c;
        }
      }
      $temp=NULL;
      foreach ($z as $index) {
        $temp .= $words[$index].' ';
      }
      $out[$i][]=trim($temp);
    }
    if (($c-$i)>1) {
      for ($j=0;$j<$c;$j++) {
        $z=array();
        $s=0;
        for ($k=1;$k<=$i;$k++) {
          $z[$k]=$j+$k-1+$s;
          if ($z[$k]>=$c) {
            $z[$k]-=$c;
          }
          $s++;
        }
        $temp=NULL;
        foreach ($z as $index) {
          $temp .= $words[$index].' ';
        }
        $out[$i][]=trim($temp);
      }
    }
  }
}
 

prints

A
B
C
D
E

A B
B C
C D
D E
E A
A C
B D
C E
D A
E B

A B C
B C D
C D E
D E A
E A B
A C E
B D A
C E B
D A C
E B D

A B C D
B C D E
C D E A
D E A B
E A B C

[hsriat]

Wait... I'm working on a general one.

Just few minutes plz...

[hsriat]

Woo!!
Done in approx 2 hours!!
No limit for number of words!! (until memory utilization is fine)[php]<?php
$string = "one two three";
$word_array = explode(" ",$string);
for ($i=count($word_array); $i>=1; $i--)
{
$word = $i == 1 ? " word" : " words";
echo "Strings containing combination of ".$i.$word.":<br>";

$flags = array();
$combination_flags = get_combination_flags(count($word_array), $i);
$flags_groups = explode(",",$combination_flags);
foreach ($flags_groups as $val)
{
$temp = chunk_split($val,1,".");
array_push($flags, explode(".", substr($temp,0,(strlen($temp)-1))));
}
for ($j=0; $j<count($flags); $j++)
{
$new_string = "";
for ($k=0; $k<count($word_array); $k++)
$new_string .= $flags[$j][$k] ? " ".$word_array[$k] : "";
trim ($new_string);
echo $new_string."<br>";
}
echo "<br>";
}

function get_combination_flags($total, $required)
{
$flag_array = array();
$bin = "";
for ($i=0; $i<$total; $i++)
$bin .= "1";
$dec = bindec($bin);
for ($i=0; $i<=$dec; $i++)
{
$num_of_chars = count_chars(decbin($i), 1);
if ($num_of_chars[49]==$required)
{
$temp = decbin($i);
$length = strlen($temp);
$pre = "";
if ($length<$total) for ($j=$length; $j<$total; $j++) $pre .= "0";
$temp = $pre.$temp;
array_push($flag_array,$temp);
}
}
return implode(",",$flag_array);
}
?>[/php]

Hope you will use it... :)

- Harpreet

[hsriat]

Output of the above is:

... removed ...

[henryrhenryr]

Hey Harpreet

That's genious! Thanks very much - I was going to settle for the 5 word one but this is really fantastic - makes my system work really nicely.

I'm not 100% sure how you got the get_combination_flags to do what it does. I'll keep trying to work it out though... really helps me learn new methods too...

Thanks again!

Henry

[hsriat]

Hey Harpreet

That's genious! Thanks very much - I was going to settle for the 5 word one but this is really fantastic - makes my system work really nicely.

I'm not 100% sure how you got the get_combination_flags to do what it does. I'll keep trying to work it out though... really helps me learn new methods too...

Thanks again!

Henry

I love to solve Mathematical Puzzles!

I'm glad to know that it really helped you!! :)

And as far as that get_combination_flags() is concerned, look at the structure of binary numbers. You will get it quickly.

[henryrhenryr]

Hi Harpreet

I've adapted it into my code and it works a dream. I'm using it to create SQL queries which count the number of occurances of any combination of words input and order them... Let me know if you're interested in the code...

Understand the binary more now - it's a good solution.

Thanks again!

Henry

[hsriat]

Hi Harpreet

I've adapted it into my code and it works a dream. I'm using it to create SQL queries which count the number of occurances of any combination of words input and order them... Let me know if you're interested in the code...

Understand the binary more now - it's a good solution.

Thanks again!

Henry

Right now I don't need anything like that. Will tell you if I'll need.

You might be doing something unique. :p