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 >
