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
Post by German Geekhttps://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
$graph = array(
'0,1' => 0,
'0,2' => 2,
...
Edit: Actually, maybe you can do it in a two-dimensional array, where no
$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...
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).
<?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),
);
http://www.sitepoint.com/data-structures-4/
Cheers,
T
Tim-Hinnerk Heuer
Blog: http://www.thheuer.com
Post by Nickolas WhitingRound 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
Post by Floyd ReslerHere's my task: A group of kids is going to be staying with different
host
Post by Floyd Reslerfamilies throughout the next 8 months. The number of kids staying with
a
Post by Floyd Reslerhost family can range from 2 to 10. When deciding which kids should
stay
Post by Floyd Reslertogether at a host family, the idea is for the system to put together
kids
Post by Floyd Reslerwho have stayed with each other the least on past weekends. So, if a
host
Post by Floyd Reslerfamily can keep 5 kids, then the group of 5 kids who have stayed
together
Post by Floyd Reslerthe 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
Post by Floyd Resleris the group that is selected. However, this approach wound of
iterating
Post by Floyd Reslerthrough 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