Re: 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.de@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 > > Twitter: @geekdenz > Blog: http://www.thheuer.com > > > On 20 October 2013 19:13, German Geek <geek.de@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 > > > > Twitter: @geekdenz > > Blog: http://www.thheuer.com > > > > > > On 20 October 2013 15:33, German Geek <geek.de@gmail.com> 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@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 > >>> õÊi*øÝI > >>> ¡êšÛlhttp://forrst.com/posts/PHP_Round_Robin_Algorithm-2zm > >>> > >>> > >>> On Tue, Oct 1, 2013 at 2:51 PM, Floyd Resler <fresler@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 > >>> > >> > >> > > >