6

開発者 、 、 、 、 がいてA、Bお互いCのD作業EをFレビューしているとします。

毎週レビューしなければならない作業を各開発者に通知し、次の基準を満たすレビュー ローテーションを生成するアルゴリズムを開発するにはどうすればよいでしょうか。

  • 同じ人物を 2 週間連続でレビューすることはできません
  • Aクローズド ループ ( reviews B、Breviews A)はありません。
  • 繰り返し始める前に、他の開発者を一度レビューするとよいでしょう。

開発者数が奇数の場合はうまくいくと思いますが、偶数の場合は苦労しています。

4

5 に答える 5

1

これは Haskell でのブルート フォースです (開始までに約 10 秒かかります)。

コード：

import Control.Monad (guard, replicateM)

developers = ["A", "B", "C", "D", "E", "F"]

combinations = filter (\x -> head x /= last x) . replicateM 2 $ developers

makeWeek week =
  if length week == length developers
     then [week]
     else do
       review <- combinations
       guard (notElem (take 1 review) (map (take 1) week)
              && notElem (drop 1 review) (map (drop 1) week)
              && notElem (reverse review) week
              && notElem review week)
       makeWeek (review:week)

solve = solve' [] where
  solve' weeks =
    if length weeks == length developers - 1
       then [weeks]
       else do
         week' <- makeWeek []
         guard (all (\x -> notElem x (concat . take (length developers - 1) $ weeks)) week')
         solve' (week':weeks)

サンプル出力:

*Main> solve
[[[["F","B"],["E","A"],["D","C"],["C","E"],["B","D"],["A","F"]]
 ,[["F","C"],["E","B"],["D","A"],["C","D"],["B","F"],["A","E"]]
 ,[["F","A"],["E","C"],["D","B"],["C","F"],["B","E"],["A","D"]]
 ,[["F","E"],["E","D"],["D","F"],["C","B"],["B","A"],["A","C"]]
 ,[["F","D"],["E","F"],["D","E"],["C","A"],["B","C"],["A","B"]]],...etc
于 2013-04-11T23:42:05.780 に答える
1

私は nieve ルートに行き、円形の配列を回転させます。したがって、第 1 週は全員が右隣の人をレビュー + 0 します。第 2 週は全員が右隣の人を + 1 レビューします。第 3 週は右 + 2 などです。

Week 1:
  A -> B
  B -> C
  ...
  F -> A
Week 2:
  A -> C
  B -> D
  ...
  F -> B
于 2013-04-11T15:58:36.667 に答える
1

繰り返しなしですべての可能なペアを取得する単純なラウンド ロビン トーナメント アルゴリズムがあります。

Arrange developers in two columns, left column reviews right one.
Fix A place
Move all others in cyclic way.

A->F
B->E 
C->D

A->B
C->F 
D->E

A->C
D->B 
E->F

A->D
E->C 
F->B

A->E
F->D 
B->C
于 2013-04-12T13:10:56.017 に答える
0

閉じたループによって、正確に 2 の長さのサイクルを参照すると仮定します。つまり、Areviews B、BreviewsCおよびCreviewsが許可されますA。

を人数nとし、0, ..., n-1それらの名前を とする。

第 1 週: personiは person のコードを確認します(i + 1) % n。

第 2 週: personiは person のコードを確認します(i + 2) % n。

...

週:クローズド ループが発生するため、n/2Personは person のコードをi 確認できません。(i + n/2) % nしたがって、 personiは代わりに person のコードを確認します(i + n/2 + 1) % n。

週n/2 + 1: 人iは人のコードをレビューします(i + n/2 + 2) % n。

...

週n - 1: 人iは人のコードを(i + 1) % nもう一度見直し、すべてが最初からやり直します。

注: 最後の (オプションの) 要件 (サイクルが再開される前に各人が他のすべての人をレビューする) に違反しています。n = 2とについてn = 4は、とにかくすべての要件を満たす解は存在しません。ベースケースn = 2は簡単です。ケースを考えてみましょうn = 4: クローズド ループを回避したい場合は、少なくとも 1 人が同じ人を 2 回続けてレビューする必要があります。(これを確認するには、考えられるすべてのレビュー関係を列挙してください)。

最後の要件が本当に必要な場合は、@groovy のソリューションを使用する必要があります。計算は非常に簡単なので、ここに残します。

于 2013-04-12T07:42:54.947 に答える