每周小组分配算法

Question

作为老师的我的一位朋友在班上有23名学生。他们需要一种算法，在14周内将学生分成2组和1组，每组3人（处理奇数学生），这样在14周内没有两对重复（一对分配给一周）。

蛮力方法效率太低，所以我想到了其他方法，矩阵表示听起来很有吸引力，还有图论。有没有人有任何想法？我能找到的问题只处理1周，而我能弄明白的是this answer。

Answer 1

Round-robin algorithm会做我的想法。

将剩余的学生添加到第二组，然后完成。

First run 
1 2 3 4 5 6 7 8 9 10 11 12 
23 22 21 20 19 18 17 16 15 14 13 

Second run 
1 23 2 3 4 5 6 7 8 9 10 11 
22 21 20 19 18 17 16 15 14 13 12 

...

Answer 2

尝试用约束来描述问题。

然后将约束传递给像ECLiPSe（而不是Eclipse）的工具，请参阅http://eclipseclp.org/。

事实上，您的问题与该网站上的高尔夫示例类似（http://eclipseclp.org/examples/golf.ecl.txt）。

Answer 3

为每个拥有所有其他学生的学生开始一组（可能是为学生减少内存消耗的bitset映射）。迭代14次，每次挑选11名学生（您将组成11个小组），为其选择合作伙伴。对于每个学生，挑选一个他们还没有参加过的小组。对于这11名学生中的一名随机学生，选择第二个合作伙伴，但要确保没有学生剩余的合作伙伴少于剩余的迭代次数。对于每个选秀节目，调整集合。

Answer 4

下面是在Haskell一个例子，这将产生14个非重复的11对的组合的基团。值'对'是从1到23的对的所有组合（例如[1,2]，[1,3]等）。然后，程序建立列表，其中每个列表是11对的14个列表（从值'对'中选择），使得没有对被重复，并且在11对列表中没有重复单个数字。如果您认为合适，只需在每周放置失踪的最后一名学生，由您决定。 （花了约三分钟来计算前开始的输出结果）：

import Data.List 
import Control.Monad 

pairs = nubBy (\x y -> reverse x == y) 
     $ filter (\x -> length (nub x) == length x) $ replicateM 2 [1..23] 

solve = solve' [] where 
    solve' results = 
    if length results == 14 
     then return results 
     else solveOne [] where 
     solveOne result = 
      if length result == 11 
       then solve' (result:results) 
       else do next <- pairs 
         guard (notElem (head next) result' 
          && notElem (last next) result' 
          && notElem next results') 
         solveOne (next:result) 
         where result' = concat result 
           results' = concat results 

一个样品从输出：

[[[12,17],[10,19],[9,18],[8,22],[7,21],[6,23],[5,11],[4,14],[3,13],[2,16],[1,15]], 
[[12,18],[11,19],[9,17],[8,21],[7,23],[6,22],[5,10],[4,15],[3,16],[2,13],[1,14]], 
[[12,19],[11,18],[10,17],[8,23],[7,22],[6,21],[5,9],[4,16],[3,15],[2,14],[1,13]], 
[[15,23],[14,22],[13,17],[8,18],[7,19],[6,20],[5,16],[4,9],[3,10],[2,11],[1,12]], 
[[16,23],[14,21],[13,18],[8,17],[7,20],[6,19],[5,15],[4,10],[3,9],[2,12],[1,11]], 
[[16,21],[15,22],[13,19],[8,20],[7,17],[6,18],[5,14],[4,11],[3,12],[2,9],[1,10]], 
[[16,22],[15,21],[14,20],[8,19],[7,18],[6,17],[5,13],[4,12],[3,11],[2,10],[1,9]], 
[[20,21],[19,22],[18,23],[12,13],[11,14],[10,15],[9,16],[4,5],[3,6],[2,7],[1,8]], 
[[20,22],[19,21],[17,23],[12,14],[11,13],[10,16],[9,15],[4,6],[3,5],[2,8],[1,7]], 
[[20,23],[18,21],[17,22],[12,15],[11,16],[10,13],[9,14],[4,7],[3,8],[2,5],[1,6]], 
[[19,23],[18,22],[17,21],[12,16],[11,15],[10,14],[9,13],[4,8],[3,7],[2,6],[1,5]], 
[[22,23],[18,19],[17,20],[14,15],[13,16],[10,11],[9,12],[6,7],[5,8],[2,3],[1,4]], 
[[21,23],[18,20],[17,19],[14,16],[13,15],[10,12],[9,11],[6,8],[5,7],[2,4],[1,3]], 
[[21,22],[19,20],[17,18],[15,16],[13,14],[11,12],[9,10],[7,8],[5,6],[3,4],[1,2]]] 

Answer 5

另一种可能性是将需要graph matching，14不同的图形匹配数。