Re: Algorithm Help
| From: | German Geek | Date: | Sun, 20 Oct 2013 06:13:50 +0000 |
| Subject: | Re: Algorithm Help | ||
| References: | 1 2 3 | Groups: | php.general |
| Request: | Send a blank email to php-general+get-322334@lists.php.net to get a copy of this message | ||
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
>>
>
>