Re: [PHP] Algorithm Help
Hi, Indeed making and maintaining the graph looks like the best approach here to tackle this problem , but what does not seem clear to me is this -- Suppose a family can host 5 children , then you need to find the set of 5 such nodes out of the total no. of nodes(assume 10) such that the total weight of all edges connecting the 5*4 nodes is minimum , how do you go about finding this set once you have constructed and maintained this graph and what will be the complexity?? On Sun, Oct 20, 2013 at 11:49 AM, German Geek geek...@gmail.com wrote: 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...@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...@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(
Re: [PHP] Algorithm Help
You don't need to maintain the history of which kids stay where unless you want to for other reasons. You just need to find the children that have staid the least amount of time together, which this approach would do for you. So, when 4 children stay together you say 1 together with 2 1 together with 3 1 together with 4 2 together with 3 2 together with 4 3 together with 4 and that's it. And then you can find the ones that staid together the least amount of time. Tim-Hinnerk Heuer Twitter: @geekdenz Blog: http://www.thheuer.com On 20 October 2013 21:53, Ayush Ladia ayushladia.for...@gmail.com wrote: Hi, Indeed making and maintaining the graph looks like the best approach here to tackle this problem , but what does not seem clear to me is this -- Suppose a family can host 5 children , then you need to find the set of 5 such nodes out of the total no. of nodes(assume 10) such that the total weight of all edges connecting the 5*4 nodes is minimum , how do you go about finding this set once you have constructed and maintained this graph and what will be the complexity?? On Sun, Oct 20, 2013 at 11:49 AM, German Geek geek...@gmail.com wrote: 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...@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...@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();
Re: [PHP] Algorithm Help
On Oct 2, 2013, at 6:23 PM, Tamara Temple tamouse.li...@gmail.com wrote: On Oct 2, 2013, at 9:05 AM, Marc Guay marc.g...@gmail.com wrote: If you have the technology handy, it could also just be easier to wipe the children's memories after each stay. Marc -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php Well played! (.. eying the black suit…. What's that funny stick you're hol….) I love it! Our director loved it too! Too funny! Thanks! Floyd -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Algorithm Help
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 fres...@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
Re: [PHP] Algorithm Help
On Oct 1, 2013, at 1:51 PM, Floyd Resler fres...@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 While definitely a tempting coding exercise, I just want to say that if this is urgent in any way, shuffling cards with the kids' names on them by hand might just be faster and less frustrating :) OTOH, if this is something you're going to have to figure out week after week, then a software solution might be handy. This is also not an *easy* problem to solve; there isn't a simple approach to optimizing this sort of thing because you're building a net between all the various kids based on past stays, in addition to the constraints of host family capacity. Thus your previous code attempts might in fact be the end result. Obviously, structuring the data is the key here. I'm thinking of 3 primary models: Kids, Hosts, and Stays. Kids and Hosts seem pretty obvious. Stays is the interesing model, and needs to have joining tables with Kids and Hosts. A Stay will have one Host, and have many Kids and a date. The algorithm then needs to make the graph where it can pull out the number of times any particular kid has stayed with another, looking something like this: Amy: Ben: 10 Jill: 3 Carlos: 7 Chen: 2 Ben: Amy: 10 Jill: 5 Carlos: 8 Chen: 3 Jill: … and so on Then you be able to pull through that graph and find the smallest number of stays for each kid. Not simple, but I hope this helps. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Algorithm Help
On 1 Oct 2013, at 19:51, Floyd Resler fres...@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? Sounds like a job for a directed graph data structure. I wish I had time to knock up a solution but I don't right now. This article should help you get started: http://www.codediesel.com/algorithms/building-a-graph-data-structure-in-php/ -Stuart -- Stuart Dallas 3ft9 Ltd http://3ft9.com/ -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Algorithm Help
It also depends on the amount of kids, families and stays. If the numbers are low, by hand may be a lot easier and faster Kind regards/met vriendelijke groet, Serge Fonville http://www.sergefonville.nl 2013/10/2 Tamara Temple tamouse.li...@gmail.com On Oct 1, 2013, at 1:51 PM, Floyd Resler fres...@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 While definitely a tempting coding exercise, I just want to say that if this is urgent in any way, shuffling cards with the kids' names on them by hand might just be faster and less frustrating :) OTOH, if this is something you're going to have to figure out week after week, then a software solution might be handy. This is also not an *easy* problem to solve; there isn't a simple approach to optimizing this sort of thing because you're building a net between all the various kids based on past stays, in addition to the constraints of host family capacity. Thus your previous code attempts might in fact be the end result. Obviously, structuring the data is the key here. I'm thinking of 3 primary models: Kids, Hosts, and Stays. Kids and Hosts seem pretty obvious. Stays is the interesing model, and needs to have joining tables with Kids and Hosts. A Stay will have one Host, and have many Kids and a date. The algorithm then needs to make the graph where it can pull out the number of times any particular kid has stayed with another, looking something like this: Amy: Ben: 10 Jill: 3 Carlos: 7 Chen: 2 Ben: Amy: 10 Jill: 5 Carlos: 8 Chen: 3 Jill: … and so on Then you be able to pull through that graph and find the smallest number of stays for each kid. Not simple, but I hope this helps. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Algorithm Help
On Oct 2, 2013, at 9:51 AM, Tamara Temple tamouse.li...@gmail.com wrote: On Oct 1, 2013, at 1:51 PM, Floyd Resler fres...@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 While definitely a tempting coding exercise, I just want to say that if this is urgent in any way, shuffling cards with the kids' names on them by hand might just be faster and less frustrating :) OTOH, if this is something you're going to have to figure out week after week, then a software solution might be handy. This is also not an *easy* problem to solve; there isn't a simple approach to optimizing this sort of thing because you're building a net between all the various kids based on past stays, in addition to the constraints of host family capacity. Thus your previous code attempts might in fact be the end result. Obviously, structuring the data is the key here. I'm thinking of 3 primary models: Kids, Hosts, and Stays. Kids and Hosts seem pretty obvious. Stays is the interesing model, and needs to have joining tables with Kids and Hosts. A Stay will have one Host, and have many Kids and a date. The algorithm then needs to make the graph where it can pull out the number of times any particular kid has stayed with another, looking something like this: Amy: Ben: 10 Jill: 3 Carlos: 7 Chen: 2 Ben: Amy: 10 Jill: 5 Carlos: 8 Chen: 3 Jill: … and so on Then you be able to pull through that graph and find the smallest number of stays for each kid. Not simple, but I hope this helps. That's the only approach I could think of. I may have to tell the director it may be a bit slow but at least she won't have to do it by hand! Thanks! Floyd -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Algorithm Help
If you have the technology handy, it could also just be easier to wipe the children's memories after each stay. Marc -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Algorithm Help
On Oct 2, 2013, at 9:05 AM, Marc Guay marc.g...@gmail.com wrote: If you have the technology handy, it could also just be easier to wipe the children's memories after each stay. Marc -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php Well played! (.. eying the black suit…. What's that funny stick you're hol….) -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
[PHP] Algorithm Help
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
Re: [PHP] Algorithm Help
On 10/1/2013 12:51 PM, Floyd Resler 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 Whatever solution you're going with will probably involve a relational database of some sort. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Algorithm Help
DB or flatfile? I would create a matrix of all kids crossed with every kid. Everytime a kid is put in a home with another kid, ++ that index. When dispatching kids, sort by index ASC. Aziz On Tue, Oct 1, 2013 at 3:01 PM, John Meyer johnme...@pueblocomputing.comwrote: On 10/1/2013 12:51 PM, Floyd Resler 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 Whatever solution you're going with will probably involve a relational database of some sort. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP] Algorithm Help
On Tue, 2013-10-01 at 15:09 -0400, Aziz Saleh wrote: DB or flatfile? I would create a matrix of all kids crossed with every kid. Everytime a kid is put in a home with another kid, ++ that index. When dispatching kids, sort by index ASC. Aziz On Tue, Oct 1, 2013 at 3:01 PM, John Meyer johnme...@pueblocomputing.comwrote: On 10/1/2013 12:51 PM, Floyd Resler 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 Whatever solution you're going with will probably involve a relational database of some sort. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php This sounds remarkably like homework, which we can't help you with unless you've got a specific problem that you're stuck with. Thanks, Ash http://www.ashleysheridan.co.uk
Re: [PHP] Algorithm Help
m 1375 GLENDALE MILFORD RD., CINCINNATI, OH 45215 On Oct 1, 2013, at 3:14 PM, Ashley Sheridan a...@ashleysheridan.co.uk wrote: On Tue, 2013-10-01 at 15:09 -0400, Aziz Saleh wrote: DB or flatfile? I would create a matrix of all kids crossed with every kid. Everytime a kid is put in a home with another kid, ++ that index. When dispatching kids, sort by index ASC. Aziz On Tue, Oct 1, 2013 at 3:01 PM, John Meyer johnme...@pueblocomputing.comwrote: On 10/1/2013 12:51 PM, Floyd Resler 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 Whatever solution you're going with will probably involve a relational database of some sort. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php This sounds remarkably like homework, which we can't help you with unless you've got a specific problem that you're stuck with. Thanks, Ash http://www.ashleysheridan.co.uk Oh, no, this is definitely not homework! :) Although it certainly seems like a homework question. This is a real world problem. I'm keeping track of which kids stay with which host families in the database. My initial approach was to start with kid 1 and see how many times the other kids have stayed with kid 1. The move on to kid 2, and so it. This gives me a score for pairs of kids. However, if say three kids are staying at a host family, what is the best way to determine which set of three kids have stayed together the least? Thanks! Floyd
Re: [PHP] Algorithm Help
Assuming you don't have to be exact, somthing similar to this might work. Assign each kid to a host family randomly for each kid, check how frequently it has been combined with the kids in its assigned family. if it is too close, swap with a different family when all kids in that family are processed, move on to the next family and repeat, excluding the first family for swapping. do the same for all families excluding the previous families. when you have completed all families, do another iteration or two of the whole process. Kind regards/met vriendelijke groet, Serge Fonville http://www.sergefonville.nl 2013/10/1 Floyd Resler fres...@adex-intl.com m 1375 GLENDALE MILFORD RD., CINCINNATI, OH 45215 On Oct 1, 2013, at 3:14 PM, Ashley Sheridan a...@ashleysheridan.co.uk wrote: On Tue, 2013-10-01 at 15:09 -0400, Aziz Saleh wrote: DB or flatfile? I would create a matrix of all kids crossed with every kid. Everytime a kid is put in a home with another kid, ++ that index. When dispatching kids, sort by index ASC. Aziz On Tue, Oct 1, 2013 at 3:01 PM, John Meyer johnme...@pueblocomputing.comwrote: On 10/1/2013 12:51 PM, Floyd Resler 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 Whatever solution you're going with will probably involve a relational database of some sort. -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php This sounds remarkably like homework, which we can't help you with unless you've got a specific problem that you're stuck with. Thanks, Ash http://www.ashleysheridan.co.uk Oh, no, this is definitely not homework! :) Although it certainly seems like a homework question. This is a real world problem. I'm keeping track of which kids stay with which host families in the database. My initial approach was to start with kid 1 and see how many times the other kids have stayed with kid 1. The move on to kid 2, and so it. This gives me a score for pairs of kids. However, if say three kids are staying at a host family, what is the best way to determine which set of three kids have stayed together the least? Thanks! Floyd