週単位のグループ割り当てアルゴリズム

Question

教師である私の友人は、クラスに23人の学生がいます。彼らは、14週に渡って2つのペアが繰り返されないように、2つのグループと3つのグループの1つのグループ（14人の学生の奇数を扱う）を割り当てるアルゴリズムが必要です（ペアは1週間に割り当てられます）。

ブルートフォースアプローチはあまりにも非効率的なので、私は他のアプローチ、マトリックス表現の魅力、グラフ理論を考えていました。誰にもアイデアはありますか？私が見つけることができた問題は、1週間だけでした。そして、this answer私はかなり分かりました。

Answer 1

Round-robin algorithm私は思っています。

残りの生徒を2番目のグループに追加すると、完了です。

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/を参照してください。

実際、あなたの問題は、そのサイトのGolfサンプル（http://eclipseclp.org/examples/golf.ecl.txt）の問題と似ています。

Answer 3

他のすべての生徒がいるすべての生徒のためのセット（おそらく、より少ないメモリ消費のための生徒へのビットセットマッピング）で始めます。 14回繰り返し、毎回パートナーを選ぶ11人の学生（あなたが結成する11のグループ）を選びます。生徒ごとに、まだグループにいないパートナーを選択します。それらの11人のランダムな学生の場合は、2番目のパートナーを選びますが、残っている反復よりもパートナーの残存が少ないことを確認してください。すべてのピックに対して、セットを調整します。

Answer 4

14非反復11-ペアの組み合わせのグループを生成するHaskellの例です。値「pairs」は、1から23までのペアのすべての組み合わせです（[1,2]、[1,3]など）。次に、プログラムは、各リストが11組の14組のリスト（値 'pairs'から選択する）であるリストを構築し、対が繰り返されず、11組の1つのリストにおいて単一の番号が繰り返されないようにする。あなたに合っていると思われる毎週最後の生徒を単に配置するのはあなた次第です。 （それは、出力結果を開始する前に、それは計算に約3分かかった）：

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 

1つのサンプルを出力から：

[[[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の異なるグラフのマッチングが必要になるかもしれません。