Page 1 of 2

random words in sentence

Posted: Tue Aug 09, 2005 9:17 am
by shiznatix
ok i have a string lets say it is 'he jumps high' ok then i have a sentence lets say it is 'when jumps high he killed the man that said that he jumps high' .

well what i need to do is find all occurences of the string in the sentence but the words of the string can be in any order in the sentence. so what im saying is i need to know that 'jumps high he' AND 'he jumps high' are in the sentence becuase it has the words in the string even though it isnt in the same order. how can i do this?

Posted: Tue Aug 09, 2005 9:23 am
by Grim...
Let me get something straight - which of these would come back as '1'?

"here is a" in "here is a load of text"
"is a here" in "here is a load of text"
"here is load" in "here is a load of text"
"is" in "here is a load of text"

Posted: Tue Aug 09, 2005 9:25 am
by anjanesh
To Grim - If I've understood correctly - only 1 and 2.

Posted: Tue Aug 09, 2005 9:26 am
by shiznatix
1, 2, and 4 but not 3

Posted: Tue Aug 09, 2005 9:30 am
by Grim...
I think (as far as I know) you are going to have to make a function to stick all the possible combinations of words into an array, then go through the array with http://uk.php.net/stristr.

Although Feyd could probably make some regex thing that to me looks like someone holding down the shift key and randomly hitting numbers, but works just the way you want it to ;)

Posted: Tue Aug 09, 2005 9:32 am
by nielsene
I'd probably do something like:

Code: Select all

$searchWords=explode(" ",$words);
$found=TRUE;
foreach($searchWords=>$aWord) {
  if (strpos($stringToSearch,$aWord)===FALSE) $found=FALSE;
  if ($found==FALSE) break;
}
if ($found) {
  // handle match
} else {
  // handle non-match
}

Posted: Tue Aug 09, 2005 9:33 am
by shiznatix
well the regex wouldnt work cause the words can be anything.

im going to try the other method you sugested

EDIT: how can i make a list of every possible order of an array?

Posted: Tue Aug 09, 2005 9:45 am
by Grim...
Yeah, that's a really good question.

I can think of a super-bad way off the top of my head... Hang on...

Posted: Tue Aug 09, 2005 9:47 am
by nielsene
shiznatix wrote: EDIT: how can i make a list of every possible order of an array?
What's the maximum number of items in your array? A full list of orderings is O(n!) so it can quickly eat up gobs of memory.....

Posted: Tue Aug 09, 2005 9:48 am
by shiznatix
the string will usually be 2 or 3 words so the globs of memory im not worrying about

Posted: Tue Aug 09, 2005 9:56 am
by feyd
why not just seperate the words being searched for into seperate elements. Find the first occurance of any of those words, toss that word. Look at the next word, is it in the list of remaining words to search for? If so, toss that word, and look at the next, and so on, and so on...

Takes care of permutations without having to create them..

Posted: Tue Aug 09, 2005 9:59 am
by nielsene
feyd wrote:why not just seperate the words being searched for into seperate elements. Find the first occurance of any of those words, toss that word. Look at the next word, is it in the list of remaining words to search for? If so, toss that word, and look at the next, and so on, and so on...

Takes care of permutations without having to create them..
Which, I think, is what my code above should do....

Posted: Tue Aug 09, 2005 10:01 am
by feyd
exactly.. I was reinforcing your idea. :) (Forgot to mention that :D)

Posted: Tue Aug 09, 2005 10:02 am
by Grim...
But the words have to be next to each other in the sentence, right?


Shiznatix, I have to ask because I'm intrigued...
Why?

Posted: Tue Aug 09, 2005 10:14 am
by nielsene
Ahh... they have to be adjacent, but order doesn't matter...

Hmm I think I'd hack up some sort of recusrive sort then:

in psuedo code:
explode the word list
loop through the word list. if you find a match, recurse using:
-- the word list minus the found word
-- the string to be searched starting after the found word