June,
Have you considered a classical Assignment Problem
formulation http://www.nist.gov/dads/HTML/assignment.html ?
It may take some artful crafting to fit your problem into
the AP, but it would be a start.
If you want to pursue that further, I may have
worked out an algorithm for it based on Keith Smillie's
help. I think the algorithm is called the Russian algorithm.
(B=)
On Sat, 11 Mar 2006, Mike Day wrote:
+ So which is worse? not changing tables (groups) or staying with
+ more than one old neighbour. Group 0 has 5 members, so if they
+ must all change group, there must be at least three in one new
+ group; alternatively, if one can stay in group 0, then the no
+ more than one previous neighbour rule can be met.
+
+ Mike
+
+ June Kim wrote:
+
+ >There are 17 people. They each belonged to four groups previously.
+ >
+ >Group 0 had five people:
+ >0
+ >1
+ >2
+ >3
+ >4
+ >
+ >Group1 had four people:
+ >5
+ >6
+ >7
+ >8
+ >
+ >Group2, ditto:
+ >9
+ >10
+ >11
+ >12
+ >
+ >Group3, ditto:
+ >13
+ >14
+ >15
+ >16
+ >
+ >I wanted to shuffle them into new groups. But there were some constraints.
+ >
+ >If possible, every person should move into a new group. For example,
+ >person 16 should not stay in the group 3. (The groups have physical
+ >locations, uh tables, and I want to change people's location)
+ >
+ >It is preferable that the people meet new people at their new groups.
+ >Meeting just one person in the previous grouping wouldn't be too bad.
+ >
+ >Person number 0, 5, 9, 10, 13, 14, 16 should be well distributed among
+ >the groups.
+ >
+ >It is preferable that person number 1, 6, 10, 16 go into each team;
+ >that is, if possible, each of them should be in different groups and
+ >well distributed among the four groups.
+ >
+ >This was a real problem I encountered a few days ago and I solved it
+ >with pencil and paper. I'd like to solve it using J but can't think of
+ >a good way of solving this kind of constraints problem in J.
+ >
+ >Any suggestions?
+ >
+ >June
+ >----------------------------------------------------------------------
+ >For information about J forums see http://www.jsoftware.com/forums.htm
+ >
+ >
+ >
+ >
+ ----------------------------------------------------------------------
+ For information about J forums see http://www.jsoftware.com/forums.htm
+
(B=) <----------my "sig"
Brian Schott
Atlanta, GA, USA
schott DOT bee are eye eh en AT gee em ae eye el DOT com
http://schott.selfip.net/~brian/
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
