Best way to traverse a single dimensional array to find combinations?

[anupamsaha]

Hello,

 

I have an array as follows:

 

$a = array('a1', 'b1', 'c1'); // this can grow to 1000+ strings as array elements

 

My objective is to traverse through the array quickly and create combination of strings taking two at a time. This means, the following will be the output:

 

array(array('a1','b1'), array('a1','c1'), array('b1','c1')); // no need to create the reverse combinations

 

I wrote the following code to achieve the same, but it's really really slow for a long array (for say, number of elements 1000+)

<?php
    $words = array('a1', 'b1', 'c1');
    $result = array();
    do {
      $word1 = array_shift($words);
      foreach($words as $word2) {
          $result[] = array($word1, $word2);
      }
    } while(count($words)>0);
    print_r($result);
?>

 

Can anybody help me to implement a faster solution for this?

 

Thanks!

[xyph]

If you have 1000 strings you can create combinations from, you're going to have tons of combinations, and they will take time to parse.

 

Yours is about the fastest you can do it. The only speed you can get out of it is changing

 

while(count($words)>0);

 

to

 

while( !empty($words) );

 

This will save you from having to calculate the size of the array every time, and instead just check if it's empty. In theory, count($words) should decrease by 1 on each loop, so you could even just do a single count, store it in a variable, and decrease it by one on each loop. Stop the loop when it reaches 0

[anupamsaha]

Thanks @xyph for your note. Let me elaborate my problem here.

 

I have a text file where the actual strings are stored. By "actual", I mean the strings to be searched. These strings are combination of two strings. Now, I have another array where all thestrings are scrambled.

 

Text file (wordlists.txt)

milliontrillion
unitdecimal
crossstraight
sumdivide
...

 

The scrambled array:

array('divide', 'trillion', 'decimal', 'million', 'straight', 'sum', 'unit',....);

 

I want to traverse through the array and concatenate two strings and mark which are the strings are found from the text file.

 

Any idea about such traversing algorithm which is fast?

 

Thanks!

[xyph]

Will the text file have lines with strings that wont be in the array?

[anupamsaha]

That's correct. Text file will have lines with strings in it and not array. Actually, the text file will have the strings those MUST be in the array. But, the array might have some words those are not part of the actual string. Make sense?

[xyph]

So every combination of two words in the text file (every line) should match some combination of two values in the array?

 

I don't think there's a faster way than what you've posted. In fact, what you posted will not cover every possible pair of values from the array. If you're comparing it to two joined words, order matters.

[anupamsaha]

Yes, I know that I didn't take the reverse order into account as that can be checked by swapping the two strings from the combination.

[xyph]

What's the point of this?

 

What problem are you trying to solve?

 

This get even more complicated when you have word combinations like

 

 

murderedam

 

is it murdered - am or murder - edam ?

 

what if all 3 of those words are in the list?

[Psycho]

One of the reasons you may be experiencing a performance issue is "how" you are checking the words against the text file. Are you reading the text file on each iteration of the loop (which would be a performance problem) or are you reading the file into a variable and checking against that on each iteration/ How big is the text file? Show some more code of what you are doing.

 

Also, where is the array of words coming from. If the words are coming from a database you can do a simple query to create all the combinations by simply joining the table on itself.