OCaml में राउंड-रॉबिन एल्गोरिदम

This is the followup question of What's the grouping plan so that every two people are grouped together just once?

असल में, मैंने राउंड रॉबिन एल्गोरिदम लागू किया है।


एल्गोरिदम द्वारा, यह जोड़े सूची उत्पन्न कर सकता है जहां तत्वों की प्रत्येक संभावित जोड़ी को एक साथ समूहीकृत किया जाता है।

उदाहरण के लिए, हमारे पास a, b, c, d है, फिर

पहले दिन, हम करते हैं

a b
c d

फिर हम समूह [(ए, सी); (बी, डी)] जैसे समूह।

फिर हम इसे घड़ी की तरह गोल करते हैं

a c
d b

फिर हम समूह [(ए, डी); (सी, बी)]।

फिर हम इसे घड़ी की तरह गोल करते हैं

a d
b c

फिर हम समूह [(ए, बी); (डी, सी)] जैसे समूह।

(नोट, a हर समय तय किया जाता है।)

अंत में मैं प्राप्त कर सकता हूँ

[(क, ग); (ख, घ)]
[(ए, डी); (ग, ख)]
[(क, ख), (घ, ग)]


ओकंप कोड यहां दिए गए हैं:

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?

2
@mamdouhalramadan धन्यवाद, लेकिन वह कार्यान्वयन सरणी का उपयोग कर रहा है
जोड़ा लेखक Jackson Tale, स्रोत
आईडीके अगर यह मदद करता है, लेकिन यहां एक अच्छा वर्णन है कि समाधान क्या हो सकता है PHP और MySQL में राउंड रॉबिन टूर्नामेंट कैसे उत्पन्न कर सकता हूं "> stackoverflow.com/questions/658727/…
जोड़ा लेखक mamdouh alramadan, स्रोत

3 उत्तर

वास्तविक डेटा पर परिचालन करके आपको घड़ी के घूर्णन की गणना करने की आवश्यकता नहीं है। आप इसे एक निश्चित सरणी (जो चीजें आप घूमते हैं) में इंडेक्स चुनने के रूप में प्रस्तुत कर सकते हैं: सरणी t r बार घुमाने के बाद, अनुक्रमणिका i घूर्णन सरणी में मूल सरणी में सूचकांक i + r पर होगा, वास्तव में (i + r) mod (Array.length t) लपेटने के लिए- चारों ओर।

इस विचार के साथ आप डेटा को घुमाने के बिना जोड़ी को गणना कर सकते हैं, बस अब तक किए गए घूर्णन की संख्या का प्रतिनिधित्व करने वाले काउंटर को बढ़ा सकते हैं। असल में, आप शायद पूरी तरह से संख्यात्मक समाधान के साथ भी आ सकते हैं जो किसी भी डेटा संरचना (चीजों से घूमने की सरणी) नहीं बनाते हैं, और इस तर्क को लागू करने के लिए विभिन्न सूचकांक के कारण नहीं बनाते हैं।

1
जोड़ा
इस तरह सरणी शामिल होगी, लेकिन ओकंपल में शुद्ध कार्यात्मक के लिए बेहतर तरीका क्या है?
जोड़ा लेखक Jackson Tale, स्रोत
अगर आप उन्हें म्यूट नहीं करते हैं तो Arrays पूरी तरह से कार्यात्मक हो सकता है।
जोड़ा लेखक gasche, स्रोत
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)|]|]
*)
1
जोड़ा

यद्यपि इस प्रश्न का उत्तर दिया गया है, लेकिन सही उत्तर एक अनिवार्य तरीके से है।

अंततः मुझे कार्यात्मक तरीके से राउंड-रॉबिन एल्गोरिदम के साथ सौदा करने का निम्न तरीका मिला।

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
0
जोड़ा