Re: Algorithm Help

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 >>> http://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 >>> >> >> >