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.de@xxxxxxxxx> 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
>
> Twitter: @geekdenz
> Blog: http://www.thheuer.com
>
>
> On 20 October 2013 19:13, German Geek <geek.de@xxxxxxxxx> 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
> >
> > Twitter: @geekdenz
> > Blog: http://www.thheuer.com
> >
> >
> > On 20 October 2013 15:33, German Geek <geek.de@xxxxxxxxx> wrote:
> >
> >> This is how I would approach/imagine it:
> >>
> >>
> >>
> https://docs.google.com/drawings/d/111RISgcHyAg8NXem4H1NXnxByRUydL8GiYlGkobJwus/edit
> >>
> >> 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
> >> #links = n*(n-1)/2
> >> 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
> >>
> >> Twitter: @geekdenz
> >> Blog: http://www.thheuer.com
> >>
> >>
> >> On 4 October 2013 02:17, Nickolas Whiting <prggmr@xxxxxxxxx> 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 <fresler@xxxxxxxxxxxxx>
> >>> 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
> >>>
> >>
> >>
> >
>
