algorithm - OCaml 中的循环算法

Question

这是What's the grouping plan so that every two people are grouped together just once?的后续问题

基本上，我实现了 Round robin algorithm .

---

通过该算法，它可以生成对列表，其中每个可能的元素对都恰好分组在一起一次。

例如，我们有a、b、c、d，那么

第一天，我们就这样做

a b
cd

然后我们像[(a,c);(b,d)]那样分组。

然后我们像这样顺时针舍入它

a c
db

然后我们像[(a,d);(c,b)]那样分组。

然后我们像这样顺时针舍入它

a d
b c

然后我们像[(a,b);(d,c)]那样分组。

(注意，a 始终是固定的。)

终于可以了

[(a,c);(b,d)]
[(a,d);(c,b)]
[(a,b);(d,c)]

---

以下是 ocaml 代码:

let split = List.fold_left (fun (l1, l2) x -> (l2, x::l1)) ([], []) 

let round l1 l2 =
  match List.rev l1, l2 with
    | _, [] | [], _ -> raise Cant_round
    | hd1::tl1, hd2::tl2 ->
      hd2::(List.rev tl1), List.rev (hd1::List.rev tl2)

let rec robin fixed stopper acc = function
  | _, [] | [], _ -> raise Cant_robin
  | l1, (hd2::tl2 as l2) -> 
    if hd2 = stopper then acc
    else robin fixed stopper ((List.combine (fixed::l1) l2)::acc) (round l1 l2)

let round_robin = function
  | [] | _::[] -> raise Cant_round_robin
  | hd::tl ->
    let l1, l2 =  in
    match split tl with 
      | _, [] -> raise Cant_round_robin
      | l1, (hd2::_ as l2) -> 
    robin hd hd2 ((List.combine (hd::l1) l2)::[]) (round l1 l2)

按照算法，代码非常简单。 有更好的实现吗？

Answer 1

let round_robin ~nplayers ~round i =
  (* only works for an even number of players *)
  assert (nplayers mod 2 = 0);
  assert (0 <= round && round < nplayers - 1);
  (* i is the position of a match,
     at each round there are nplayers/2 matches *)
  assert (0 <= i && i < nplayers / 2);
  let last = nplayers - 1 in
  let player pos =
    if pos = last then last
    else (pos + round) mod last
  in
  (player i, player (last - i))

let all_matches nplayers =
  Array.init (nplayers - 1) (fun round ->
    Array.init (nplayers / 2) (fun i ->
      round_robin ~nplayers ~round i))

let _ = all_matches 6;;
(**
[|[|(0, 5); (1, 4); (2, 3)|];
  [|(1, 5); (2, 0); (3, 4)|];
  [|(2, 5); (3, 1); (4, 0)|];
  [|(3, 5); (4, 2); (0, 1)|];
  [|(4, 5); (0, 3); (1, 2)|]|]
*)