你如何开发一个开发者评论队列旋转的算法?

paut 发布于 2019-03-09 algorithm 最后更新 2019-03-09 14:32 3 浏览

假设您有开发人员ABCDEF,并且他们审查彼此的工作。 你如何开发一个算法来生成一个评论轮转,告诉每个开发者他们每周都要检查哪些工作,并且满足这些标准:

  • 您无法连续两周查看同一个人
  • 不能有闭环(A条评论BB条评论A)
  • 如果您在开始重复之前先查看每个其他开发者,那就太好了。
我认为我可以让它与奇数个开发者合作,但我正在挣扎偶数。
已邀请:

mest

赞同来自:

我似乎找到了一个受Round Robin轮换启发的解决方案。 对于开发人员ABCDEF 你修复了一个开发人员,比如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

taut

赞同来自:

我会认为,通过闭环,你指的长度正好2。也就是说,它是允许的A评论B的周期,B回顾CC评论A。 让n为人数,让0, ..., n-1成为他们的名字。 第1周: 人i审查人(i + 1) % n的代码。 第2周:人i审查人员代码(i + 2) % n。 ... 周n/2:人i不能审查人(i + n/2) % n的代码,因为这将导致一个闭环。因此,人i反而审查人(i + n/2 + 1) % n的代码。 周n/2 + 1:人i审查人员代码(i + n/2 + 2) % n。 ... 周n - 1:人i再次审查人(i + 1) % n的代码,一切都重新开始。 注意:违反了您的上一个(可选)要求(每个人在周期重新开始之前审核其他人)。对于n = 2n = 4,无论如何都不存在满足所有要求的解决方案。基础案例n = 2是微不足道的。考虑案例n = 4:如果您想避免闭环,至少有一个人必须连续两次审查同一个人。 (只需枚举所有可能的审核关系即可查看)。 如果你真的需要你的最后一个要求,你将不得不使用@ groovy的解决方案。我会离开我的,因为它很容易计算。

non_at

赞同来自:

有简单的round-robin tournament algorithm可以在不重复的情况下获得所有可能的对。

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

eomnis

赞同来自:

我会走向nieve路线并旋转一个圆形阵列。所以第1周每个人都会评论他们的权利+ 0。第2周每个人都会评论他们的权利+ 1.第3周,右+ 2等。

Week 1:
  A -> B
  B -> C
  ...
  F -> A
Week 2:
  A -> C
  B -> D
  ...
  F -> B

ivel

赞同来自:

这是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