# Re: [PHP] Algorithm Help

```Hi,
Indeed making and maintaining the graph looks like the best approach here
to tackle this problem , but what does not seem clear to me is this --
"Suppose a family can host 5 children , then you need to find the set of 5
such nodes out of the total no. of nodes(assume 10) such that the total
weight of all edges connecting the 5*4 nodes is minimum " ,
how do you go about finding this set once you have constructed and
maintained this graph and what will be the complexity??```
```

On Sun, Oct 20, 2013 at 11:49 AM, German Geek <geek...@gmail.com> wrote:

> Oh and it also assumes that you don't do
> \$graph->together('A','B');
> // ...
> \$graph->together('B', 'A'); //!! NO!
>
> If this has to be catered for you could simply sort them when inserting:
>     public function together(\$who, \$with) {
>         \$sorted = array(\$who, \$with);
>         sort(\$sorted);
>         \$who = \$sorted[0];
>         \$with = \$sorted[1];
>         if (!isset(\$this->data[\$who])) {
>             \$this->data[\$who] = array();
>         }
>         if (!isset(\$this->data[\$who][\$with])) {
>             \$this->data[\$who][\$with] = 1;
>             return;
>         }
>         \$this->data[\$who][\$with]++;
>     }
>
> for the together function.
>
> Tim-Hinnerk Heuer
>
> Blog: http://www.thheuer.com
>
>
> On 20 October 2013 19:13, German Geek <geek...@gmail.com> wrote:
>
> > Try this class:
> >
> > <?php
> >
> > // ASSUMES NAMES DON'T HAVE "|" IN THEM!! YOU COULD USE ANOTHER
> > // CHARACTER COMBO IF NEEDED AND explode ON THAT
> >
> > class Graph {
> >     protected \$data = null;
> >
> >     public function __construct(\$init = array()) {
> >         \$this->data = \$init;
> >     }
> >
> >     public function together(\$who, \$with) {
> >         if (!isset(\$this->data[\$who])) {
> >             \$this->data[\$who] = array();
> >         }
> >         if (!isset(\$this->data[\$who][\$with])) {
> >             \$this->data[\$who][\$with] = 1;
> >             return;
> >         }
> >         \$this->data[\$who][\$with]++;
> >     }
> >     public function getLeast(\$n = 1) {
> >         \$values = array();
> >         foreach (\$this->data as \$who => \$withs) {
> >             foreach (\$withs as \$kwith => \$vwith) {
> >                 \$values[\$who .'|'. \$kwith] = \$vwith;
> >             }
> >         }
> >         asort(\$values);
> >         \$nvalues = array_slice(\$values, 0, \$n);
> >         \$pairs = array();
> >         foreach (\$nvalues as \$k => \$v) {
> >             \$parts = explode('|', \$k);
> >             \$pairs[] = array(\$parts[0], \$parts[1]);
> >         }
> >         return \$pairs;
> >     }
> >     public function __toString() {
> >         return print_r(\$this->data, true);
> >     }
> > }
> >
> > \$graph = new Graph();
> >
> > \$graph->together('A', 'B');
> > \$graph->together('A', 'B');
> > \$graph->together('B', 'C');
> > \$graph->together('A', 'C');
> > \$graph->together('B', 'D');
> > \$graph->together('B', 'D');
> > \$graph->together('B', 'D');
> > \$graph->together('B', 'D');
> > \$graph->together('B', 'D');
> >
> > echo \$graph;
> >
> > \$least = \$graph->getLeast(2);
> >
> > print_r(\$least);
> >
> >
> > Tim-Hinnerk Heuer
> >
> > Blog: http://www.thheuer.com
> >
> >
> > On 20 October 2013 15:33, German Geek <geek...@gmail.com> wrote:
> >
> >> This is how I would approach/imagine it:
> >>
> >>
> >>
> >>
> >> Tom has been with Andrew 0 times.
> >> Tom has been with Shelly 1 time.
> >> Christine has been with Andrew 2 times.
> >> ...
> >>
> >> So the Graph maintains who has been with who how often.
> >>
> >> For 10 or even 20 kids you might be able to go through all links (brute
> >> force).
> >>
> >> The number of links (including the ones with 0 weight) is
> >> which is the number of links you have to maintain and then check when
> you
> >> want to know who should go with whom.
> >>
> >> So, if
> >> n=10: #links = 10*9/2 = 45
> >> n=20: #links = 20*19/2 = 190
> >> n=30: #links = 30*29/2 = 435
> >>
> >> I think even for reasonably large groups a computer can do the job
> >> easily. I would find it quite hard to do it on paper though, so I think
> you
> >> should program it.
> >>
> >> You could simply store the graph in an array, and then optionally
> persist
> >> it to a db or file:
> >>
> >> You would get e.g.:
> >>
> >> \$graph = array(
> >>   '0,1' => 0,
> >>   '0,2' => 2,
> >> ...
> >>
> >> Edit: Actually, maybe you can do it in a two-dimensional array, where no
> >> node is connected to itself:
> >>
> >> \$n=4;
> >> function init() {
> >>   global \$n;
> >>   \$graph = array();
> >>   for (\$i = 0; \$i < \$n; ++\$i) {
> >>     \$graph[\$i] = array();
> >>     for (\$j = 0; \$j < \$n; ++\$j) {
> >>       \$graph[\$i][\$j] = 0;
> >>     }
> >>   }
> >>   return \$graph;
> >> }
> >>
> >> \$graph = init();
> >>
> >> Sorry, I might be running a bit out of time here...
> >>
> >> You can use an implementation of a graph, for example this one:
> >>
> >>
> http://pear.php.net/package/Structures_Graph/docs/latest/li_Structures_Graph.html
> >>
> >> But it might be overkill as the 2-dimensional array would even do the
> >> trick and there might be less overhead although you are requiring more
> >> space than needed (n*(n-1)/2+n cells more to be exact).
> >>
> >> You could store it in a hashmap/associative array like this:
> >> <?php
> >>  \$graph = array(
> >>    'A' => array('B' => 1, 'F' => 2),
> >>    'B' => array('A' => 3, 'D' => 4, 'E' => 5),
> >>    'C' => array('F' => 6),
> >>    'D' => array('B' => 7, 'E' => 8),
> >>    'E' => array('B' => 9, 'D' => 10, 'F' => 11),
> >>    'F' => array('A' => 12, 'E' => 13, 'C' => 14),
> >>  );
> >>  (Sorry if large font). Source of idea:
> >> http://www.sitepoint.com/data-structures-4/
> >>
> >> Cheers,
> >> T
> >>
> >> Tim-Hinnerk Heuer
> >>
> >> Blog: http://www.thheuer.com
> >>
> >>
> >> On 4 October 2013 02:17, Nickolas Whiting <prg...@gmail.com> wrote:
> >>
> >>> Round Robin algorithm should solve this and is a fairly quick alogrithm
> >>> ...
> >>> http://en.wikipedia.org/wiki/Round-robin
> >>>
> >>> An example can be found
> >>> http://forrst.com/posts/PHP_Round_Robin_Algorithm-2zm
> >>>
> >>>
> >>> On Tue, Oct 1, 2013 at 2:51 PM, Floyd Resler <fres...@adex-intl.com>
> >>> wrote:
> >>>
> >>> > Here's my task: A group of kids is going to be staying with different
> >>> host
> >>> > families throughout the next 8 months.  The number of kids staying
> >>> with a
> >>> > host family can range from 2 to 10.  When deciding which kids should
> >>> stay
> >>> > together at a host family, the idea is for the system to put together
> >>> kids
> >>> > who have stayed with each other the least on past weekends.  So, if a
> >>> host
> >>> > family can keep 5 kids, then the group of 5 kids who have stayed
> >>> together
> >>> > the least will be chosen.
> >>> >
> >>> > I can't think of an easy, quick way to accomplish this.  I've tried
> >>> > various approaches that have resulted in a lot of coding and being
> very
> >>> > slow.  My idea was to give each group of kids a score and the lowest
> >>> score
> >>> > is the group that is selected.  However, this approach wound of
> >>> iterating
> >>> > through several arrays several times which was really slow.  Does
> >>> anyone
> >>> > have any ideas on this puzzle?
> >>> >
> >>> > Thanks!
> >>> > Floyd
> >>> >
> >>> >
> >>> > --
> >>> > PHP General Mailing List (http://www.php.net/)
> >>> > To unsubscribe, visit: http://www.php.net/unsub.php
> >>> >
> >>> >
> >>>
> >>>
> >>> --
> >>> Nickolas Whiting
> >>> Freelance Consultant
> >>>
> >>
> >>
> >
>
```