By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
438,216 Members | 1,013 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 438,216 IT Pros & Developers. It's quick & easy.

generating permutations and combinations...

100+
P: 103
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
Feb 28 '08 #1
Share this Question
Share on Google+
10 Replies


ronverdonk
Expert 2.5K+
P: 4,258
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
Feb 28 '08 #2

100+
P: 103
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.

Expand|Select|Wrap|Line Numbers
  1. $phrase="A B C D E";
  2. $words=explode(' ',$phrase);
  3. $c=count($words);
  4. $out=array();
  5. for ($i=1;$i<=$c;$i++) {
  6.   if ($i==1) {
  7.     foreach ($words as $w) { 
  8.       $out[$i][]=$w; 
  9.     }
  10.   }
  11.   if ($i==2) {
  12.     for ($j=0;$j<$c;$j++) {
  13.       $next=$j+1;
  14.       if ($next>=$c) {
  15.         $next=$next-$c;
  16.       }
  17.       $out[$i][]= "{$words[$j]} {$words[$next]}";
  18.     }
  19.     if (($c-$i)>1) {
  20.       for ($j=0;$j<$c;$j++) {
  21.         $next=$j+2;
  22.         if ($next>=$c) {
  23.           $next=$next-$c;;
  24.         }
  25.         $out[$i][]= "{$words[$j]} {$words[$next]}";
  26.       }
  27.     }
  28.   }
  29. }
  30.  
Feb 28 '08 #3

100+
P: 103
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?

Expand|Select|Wrap|Line Numbers
  1. $phrase="A B C D E";
  2. $words=explode(' ',$phrase);
  3. $c=count($words);
  4. $out=array();
  5. for ($i=1;$i<$c;$i++) {
  6.   if ($i==1) {
  7.     foreach ($words as $w) {
  8.       $out[$i][]=$w; 
  9.     }
  10.   }
  11.   else {
  12.     for ($j=0;$j<$c;$j++) {
  13.       $z=array();
  14.       for ($k=1;$k<=$i;$k++) {
  15.         $z[$k]=$j+$k-1;
  16.         if ($z[$k]>=$c) {
  17.           $z[$k]-=$c;
  18.         }
  19.       }
  20.       $temp=NULL;
  21.       foreach ($z as $index) {
  22.         $temp .= $words[$index].' ';
  23.       }
  24.       $out[$i][]=trim($temp);
  25.     }
  26.     if (($c-$i)>1) {
  27.       for ($j=0;$j<$c;$j++) {
  28.         $z=array();
  29.         $s=0;
  30.         for ($k=1;$k<=$i;$k++) {
  31.           $z[$k]=$j+$k-1+$s;
  32.           if ($z[$k]>=$c) {
  33.             $z[$k]-=$c;
  34.           }
  35.           $s++;
  36.         }
  37.         $temp=NULL;
  38.         foreach ($z as $index) {
  39.           $temp .= $words[$index].' ';
  40.         }
  41.         $out[$i][]=trim($temp);
  42.       }
  43.     }
  44.   }
  45. }
  46.  
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
Feb 28 '08 #4

hsriat
Expert 100+
P: 1,654
Wait... I'm working on a general one.

Just few minutes plz...
Feb 28 '08 #5

hsriat
Expert 100+
P: 1,654
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
Feb 28 '08 #6

hsriat
Expert 100+
P: 1,654
Output of the above is:
Expand|Select|Wrap|Line Numbers
  1. ... removed ...
Feb 28 '08 #7

100+
P: 103
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
Feb 29 '08 #8

hsriat
Expert 100+
P: 1,654
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.
Feb 29 '08 #9

100+
P: 103
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
Feb 29 '08 #10

hsriat
Expert 100+
P: 1,654
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
Feb 29 '08 #11

Post your reply

Sign in to post your reply or Sign up for a free account.