OCaml中的循环算法
OCaml中的循环算法
提问于 2013-12-02 15:46:26
这是分组计划是什么，使每两个人只聚一次？的后续问题
基本上，我实现了循环算法。
通过该算法，它可以生成对列表，其中每一对可能的元素被精确地组合在一起一次。
例如，我们有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代码：
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)该代码非常直接地遵循该算法。有更好的植入吗？
回答 3
Stack Overflow用户
回答已采纳
发布于 2013-12-03 13:58:37
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)|]|]
*)Stack Overflow用户
发布于 2013-12-03 10:10:08
您不需要通过对实际数据进行操作来计算顺时针旋转。您可以将其表示为在固定数组(旋转的事物)中选择索引:在旋转数组的t r次数之后，旋转数组中的索引i处的元素将位于原始数组中的索引i+r，实际上，(i+r) mod (Array.length t)将进行环绕。
有了这个想法，您可以计算配对而不移动数据，只需增加一个计数器，表示到目前为止执行的旋转次数。事实上，您甚至可能会想出一个纯粹的数值解决方案，它不会创建任何数据结构(要旋转的事物的数组)，以及应用这种推理的各种索引的原因。
Stack Overflow用户
发布于 2014-01-13 12:17:24
虽然这个问题已经回答了，但正确的答案是以一种势在必行的方式。
最后，我发现以下处理循环算法的方法在功能上更简单。
let round l1 l2 = let move = List.hd l2 in move::l1, (List.tl l2)@[move]
let combine m l1 l2 =
let rec comb i acc = function
|[], _ | _, [] -> acc
|_ when i >= m -> acc
|hd1::tl1, hd2::tl2 -> comb (i+1) ((hd1,hd2)::acc) (tl1,tl2)
in
comb 0 [] (l1,l2)
let round_robin l =
let fix = List.hd l in
let half = (List.length l)/2 in
List.fold_left (
fun (acc, (l1, l2)) _ -> (combine half (fix::l1) l2)::acc, round l1 l2
) ([], (List.tl l, List.rev l)) l |> fst |> List.tl页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20332184
复制相关文章
相似问题
腾讯云开发者
