2

これは、 2 人ごとに 1 回だけグループ化するためのグループ化計画は何ですか? のフォローアップの質問です。

基本的に、ラウンドロビンアルゴリズムを実装しました。

このアルゴリズムにより、可能な要素の各ペアが 1 回だけグループ化されたペア リストを生成できます。

たとえば、次のよう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)

コードは、アルゴリズムに従って非常に単純です。より良い実装はありますか？

4

3 に答える 3

1

実際のデータを操作して時計回りの回転を計算する必要はありません。固定配列 (回転するもの) のインデックスを選択することで表現できます: 配列t r回回転した後、回転した配列のインデックスの要素は元の配列のiインデックスi+rになり、実際(i+r) mod (Array.length t)にはラップアラウンドします。

このアイデアを使用すると、データを移動することなく、これまでに実行された回転数を表すカウンターをインクリメントするだけで、ペアリングを計算できます。実際、データ構造 (回転させる対象の配列) を作成しない純粋に数値的なソリューションと、この推論を適用するためのさまざまなインデックスの理由を考え出すこともできます。

于 2013-12-03T10:10:08.183 に答える
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)|]|]
*)
于 2013-12-03T13:58:37.907 に答える
0

この質問には回答済みですが、正解は必須の方法です。

最終的に、ラウンドロビンアルゴリズムを機能的に簡単に処理する次の方法を見つけました。

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
于 2014-01-13T12:17:24.780 に答える