You don't need to maintain the history of which kids stay where unless you want to for other reasons. You just need to find the children that have staid the least amount of time together, which this approach would do for you.
So, when 4 children stay together you say 1 together with 2 1 together with 3 1 together with 4 2 together with 3 2 together with 4 3 together with 4 and that's it. And then you can find the ones that staid together the least amount of time. Tim-Hinnerk Heuer Twitter: @geekdenz Blog: http://www.thheuer.com On 20 October 2013 21:53, Ayush Ladia <ayushladia.for...@gmail.com> wrote: > 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 >> >> Twitter: @geekdenz >> 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 >> > >> > Twitter: @geekdenz >> > 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: >> >> >> >> >> >> >> 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 <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 >> >>> >> >> >> >> >> > >> > >
