algorithm - 每周分组分配算法

Question

我的一个朋友是老师，一个班有23个学生。他们需要一种算法，在 14 周内将学生分成 2 人一组和 3 人一组（处理奇数学生），这样在 14 周内没有两对重复（一对被分配到一个星期）。

蛮力方法效率太低，所以我在考虑其他方法，矩阵表示听起来很吸引人，还有图论。有没有人有任何想法？我能找到的问题只需要 1 周就可以解决，而这个答案我完全可以弄清楚。

Answer 1

我认为循环算法可以解决问题。

将剩余的学生添加到第二组，您就完成了。

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

另一种可能性可能是图匹配，需要 14 个不同的图匹配。

Answer 3

尝试用约束来描述问题。

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

事实上，您的问题似乎与该网站 ( http://eclipseclp.org/examples/golf.ecl.txt ) 上的 Golf 示例类似。

Answer 4

从包含所有其他学生的每个学生的集合开始（可能是对学生的位集映射以减少内存消耗）。重复 14 次，每次选择 11 名学生（对于您将组成的 11 个小组），您将为他们选择合作伙伴。对于每个学生，选择一个他们尚未加入小组的伙伴。对于这 11 个学生中的一个随机学生，选择第二个伙伴，但要确保没有学生的剩余伙伴少于剩余的迭代次数。对于每一个选择，调整集合。

Answer 5

这是 Haskell 中的一个示例，它将生成 14 个非重复 11 对组合的组。值“pairs”是从 1 到 23 的所有对的组合（例如，[1,2]、[1,3] 等）。然后程序构建列表，其中每个列表是 11 对的 14 个列表（从值 'pairs' 中选择），这样在一个 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]]]