在OCaml的循环算法 [英] Round-robin algorithm in OCaml
问题描述
这是<一的后续问题href="http://stackoverflow.com/questions/20312670/whats-the-grouping-plan-so-that-every-two-people-are-grouped-together-just-once">What's分组计划，使每两个人组合在一起，只有一次？
基本上，我实现了循环算法。
通过该算法，也可以产生，其中每一个可能的一对元件被分在一起正好一次对列表
例如，我们有 A，B，C，D ，然后
在第一天，我们做
A B
C D
然后我们组像[（A，C）;（B，D）]。
然后我们顺时针圆像
A C
D B
然后我们组像[（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的code：
让分裂= List.fold_left（FUN（L1，L2）x - ＆GT;（12，X :: L1））（[] []）
让圆L1 L2 =
比赛List.rev L1，L2与
| _，[] | [] _ - ＆GT;提高Cant_round
| HD1 :: TL1，HD2 :: TL2 - ＆GT;
HD2：:( List.rev TL1），List.rev（HD1 :: List.rev TL2）
让拍摄罗宾固定塞ACC =功能
| _，[] | [] _ - ＆GT;提高Cant_robin
| L1，（HD2 :: TL2为L2） - ＆GT;
如果HD2 =塞，然后ACC
否则循环固定塞（（List.combine（固定:: L1）12）:: ACC）（圆L1 L2）
让round_robin =功能
| [] | _ :: [] - GT;提高Cant_round_robin
|高清:: TL - ＆GT;
让L1，L2 =在
比赛分体TL与
| _，[] - GT;提高Cant_round_robin
| L1，（HD2 :: _为L2） - ＆GT;
罗宾高清HD2（（List.combine（HD :: L1）12）:: []）（圆L1 L2）
在code是相当直截了当以下的算法。 有没有更好的implmentation？
让round_robin〜nplayers〜一轮I =
（*仅适用于偶数的玩家*）
断言（nplayers模2 = 0）;
断言（0℃=圆形＆安培;＆安培;圆形＆所述; nplayers - 1）;
（*我是一个匹配的位置，
在每一轮有nplayers / 2场比赛*）
断言（0℃= I＆安培;＆安培; I＆所述; nplayers / 2）;
让最后= nplayers - 1
让玩家POS =
如果pos =最后再持续
其他（POS +圆）mod去年
在
（我的球员，球员（最后 - 我））
让all_matches nplayers =
Array.init（nplayers - 1）（有趣的圆 - ＆GT;
Array.init（nplayers / 2）（乐趣我 - ＆GT;
round_robin〜nplayers〜一轮I））
让_ = 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）|] |]
*）
This is the followup question of What's the grouping plan so that every two people are grouped together just once?
Basically, I implemented the Round robin algorithm.
By the algorithm, it can generate pairs list where each possible pair of elements are grouped together exactly once.
For example, we have a, b, c, d, then
On first day, we do
a b
c d
Then we group like [(a,c);(b,d)].
Then we round it clockwise like
a c
d b
Then we group like [(a,d);(c,b)].
Then we round it clockwise like
a d
b c
Then we group like [(a,b);(d,c)].
(Note, a is fixed all the time.)
Finally I can get
[(a,c);(b,d)]
[(a,d);(c,b)]
[(a,b);(d,c)]
Here are the ocaml code:
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)
The code is quite straight forward following the algorithm. Is there a better implmentation?
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)|]|]
*)
这篇关于在OCaml的循环算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
