recursive / non-recursive logic - please help

[skibum]

Hi all,

 

One thing I struggle really struggle with is recursive logic and right now I am having a total mental blank.  The problem can be conceptualized as follows.

 

I have an array of objects that have a score and are linked to 0-n other objects.  Imagine a 5x5 matrix of objects a la....

 

A B C D E

F G H I  J

K L M N O

P Q R S T

U V W X Y

 

where each object is linked to it's neighbour (A is linked to B, F & G) and each object (lets call it a Foo) has a score.

In reality, the linkages are 0-n other objects but this matrix will do for now.  Putting all the Foos ordered by score into an array, I want to find the order of x selected Foo objects that are linked (or return FALSE if no possible linkage exists).  In other words, I want to find and ordered combo of the top x scored Foos (if one exists).

 

So, I need a function getLinkedFoos($fooList) that returns an array containing the Foo objects in order they link. If there are multiple solutions, the first one the algorithm finds is ok  As an example.....A-F-K-L-G could return K-F-L-G-A or F-L-K-G-A but not A-L-F-G-K.  A-Y would return FALSE (no linked combos).

 

This should just be a recursive problem like probing all the directories in a file system.  In this case, checking whether a linkage exists requires a database call so I think it would be better to just set up a 2D array of connections at the start of the function call to save on overhead.  Unfortunately, I am just getting myself lost in the recursive logic and need help with....

 

getLinkedFoos($fooList)

{

  $results = array();

  $links = array();

  foreach($fooList as $foo)

  {

    $links[] = $foo->getLinks(); // returns an array of foos it is linked to.  Doing this way to save on database overhead.

  }

  // much help needed here as my brain has exploded

  // should I used nested foreach/while loops or call the function itself again? arhh, I just can't get my head around it!

return $results;

}