Implementasi Algoritma Round-robin Schedule Sederhana

Round-robin Schedule Algorithm merupakan algoritma yang digunakan untuk membuat sebuah jadwal pertandingan yang digunakan oleh Round-robin tournament seperti salah satunya adalah FIFA World Cup. Dengan algoritma ini, partisipan pertandingan akan dibagi lawan mainnya seadil mungkin (termasuk posisi home dan away). So, ingin tahu kan bagaimana cara mereka membagi jadwal pertandingannya?

Pada tulisan kali ini, saya akan menjelaskan algoritma Round-robin versi sederhana yang mana masih perlu dikembangkan lebih jauh. Sebelum masuk tahap implementasi, ada beberapa kelemahan yang harus saya terangkan terlebih dahulu. Asumsikan ada 5 partisipan yang direpresentasikan sebagai [1, 2, 3, 4, 5].

Kelemahannya:

1. Partisipan 1 selalu di bagian "home".
2. Partisipan 1 bermain 5 kali yang mana seharusnya 4 kali agar adil.

Well, algoritma ini belum bisa mengatasi partisipan yang jumlahnya ganjil. Dan, apabila genap pun, partisipan 1 selalu mendapat home. Artinya, algoritma sederhana ini masih belum bisa dikatakan adil. Di tulisan berikutnya, akan kembali saya jelaskan mengenai algoritma ini yang telah dikembangkan menggunakan Berger tables.

Algoritma

Langkah-langkah untuk implementasi algoritma ini adalah:

1. Ambil daftar partisipan
=> [1, 2, 3, 4, 5, 6]

2. Buat daftar tadi menjadi dua (dibagi 2)
=> [1, 2, 3] [4, 5, 6]

3. Asumsikan daftar yang dibagi dua adalah A dan B
=> A = [1, 2, 3]
=> B = [4, 5, 6]

4. Posisi B dibalik (reverse)
=> A = [1, 2, 3]
=> B = [6, 5, 4]

5. Ambil data sebagai Round 1
=> Round 1:
=> 1 vs 6
=> 2 vs 5
=> 3 vs 4

6. Ubah daftar A menjadi [1, (data pertama B), ..., (hapus data terakhir)]
=> A = [1, 6, 2]

7. Ubah daftar B menjadi [(hapus data pertama), ..., (data terakhir A)]
=> B = [5, 4, 3]

8. Daftar yang sudah diubah menjadi Round berikutnya
=> A = [1, 6, 2]
=> B = [5, 4, 3]
=>
=> Round 2
=> 1 vs 5
=> 6 vs 4
=> 2 vs 3

9. Ulangi langkah 6, 7, dan 8 hingga Round habis (sebanyak N).

Dimana N adalah
- (banyaknya partisipan - 1) jika jumlah partisipannya genap
- (banyaknya partisipan) jika jumlah partisipannya ganjil

Dalam kasus di atas (partisipan 6, genap) maka N = (6 - 1) = 5.
Berarti, jumlah Round-nya sebanyak 5.

Tabel perpindahan data kira-kira seperti di bawah. Bagian yang diberi kutip adalah data yang dipindahkan.

1, 2, 3, 4
8, 7, 6, 5

1, "8", 2, 3
7, 6, 5, "4"

1, "7", 8, 2
6, 5, 4, "3"

...

Dan seterusnya.

Apabila kamu tertarik melihat implementasinya dengan bahasa Haskell, kamu bisa melihatnya di repository saya yaitu wisn/halgorithms. Adapun cuplikan kodenya sebagai berikut.

-- Create the schedule. Here is the main Round-robin Schedule Algorithm
schedulizer :: [a] -> [[(a, a)]]
schedulizer list = makesSchedule list (length list) (-1)
  where
    makesSchedule :: [a] -> Int -> Int -> [[(a, a)]]
    makesSchedule _ _ 0        = []
    makesSchedule list n games =
      let games'  = if games == (-1)
                      then do
                        if even n then (n - 1) else n
                      else games

          middle  = n `div` 2
          divide  = splitAt middle list

          left  = fst divide
          right = if even n
                     then (reverse . snd) divide
                     else (reverse . init . snd) divide

          zipped = zip left right
      in [zipped] ++ makesSchedule (rotater list) n (games' - 1)

Untuk melihat atau mencoba secara langsung, kamu bisa buka IDEOne berikut.

Demikian tulisan yang dapat saya bagikan kali ini. Sampai bertemu di lain waktu!