6

假设您有开发人员A, B, C, D, E,F并且他们互相审查彼此的工作。

您如何开发一种算法来生成审查轮换，告诉每个开发人员他们每周必须审查哪些工作并满足以下标准：

  • 您不能连续两周审查同一个人
  • 不能有闭环（A评论B，B评论A）
  • 如果您在开始重复之前对其他开发人员进行一次审查，那就太好了。

我想我可以让它与奇数个开发人员一起工作，但我正在努力解决偶数个问题。

4

5 回答 5

1

我似乎找到了一个受 Round Robin 轮换启发的解决方案。

对于开发人员A, B, C, D, E,F

你修复了一个开发人员，比如说A。然后顺时针旋转其余部分。

然后：

  • 第一行的每个人都在评论他们下面的人
  • 底行的每个人都检查他们上方和对角线右侧的人

第 1 周：

A B C
D E F

AD
BE
CF
DB
EC
FA

第 2 周：

A D B
E F C

AE
DF
BC
ED
FB
CA

第 3 周：

A E D
F C B

AF
EC
DB
FE
CD
BA

第 4 周：

A F E
C B D

AC
FB
ED
CF
BE
DA

第 5 周：

A C F
B D E

AB
CD
FE
BC
DF
EA

尽管它仍然表现出一些人永远不会遇到其他人的不需要的属性，例如B避免D。

于 2013-04-12T15:21:26.037 回答
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 回答
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

这是 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 回答
0

我将假设通过闭环，您指的是长度正好为 2 的循环。也就是说，允许Areviews B、BreviewsC和Creviews A。

设n人数，设0, ..., n-1姓名。

第 1 周： Personi审查 person 的代码(i + 1) % n。

第 2 周： Personi审查 person 的代码(i + 2) % n。

...

Week n/2： Personi 无法查看person 的代码(i + n/2) % n，因为这会导致闭环。因此， personi反而审查了 person 的代码(i + n/2 + 1) % n。

周n/2 + 1：人i审查人的代码(i + n/2 + 2) % n。

...

Week n - 1: Person再次i审查 person 的代码(i + 1) % n，一切重新开始。

注意：违反了您的最后一个（可选）要求（每个人在循环再次开始之前审查每个其他人）。对于n = 2和n = 4，无论如何都不存在满足所有要求的解决方案。基本情况n = 2是微不足道的。考虑这种情况n = 4：如果你想避免闭环，至少一个人必须连续两次审查同一个人。（只需列举所有可能的评论关系即可看到这一点）。

如果您真的需要最后一个要求，则必须使用@groovy 的解决方案。我会把我的留在这里，因为它很容易计算。

于 2013-04-12T07:42:54.947 回答