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@xxxxxxxxx> 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@xxxxxxxxx> 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@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
>>>
>>
>>
>
