総当たり戦の日程作成 in Scheme DouKaku?

総当たり戦の日程作成

任意の偶数Nのチームの総当たり戦を最短日数（N-1日）で行う場合の日程表を１つ作成してください。

解はひとつではない場合もあります。
もし、余力があれば、全ての可能性も求めてください。

これは、スポーツスケジューリングと言う分野の問題で、数学的には、カークマンの問題と言うのが近いようです。

例えば、４チームであれば、

1-2 3-4
1-3 2-4
1-4 2-3

６チームであれば

1-2 3-4 5-6 
1-3 2-5 4-6 
1-4 2-6 3-5 
1-5 2-4 3-6 
1-6 2-3 4-5

が解のひとつです。

see: カークマンの組分け

post comment

Posted feedbacks - Scheme

参考にあったアルゴリズムを使いました。

(define (kirkman-2 n)
  (define (first n)
    (append '((1 2)) (comb 3 n)))
  (define (comb low high)
    (if (= (- high low) 1)
    (list (list low high))
    (cons (list low high)(comb (+ low 1) (- high 1)))))
  (define (rotate m n list)
    (map
     (lambda (ilist) (map (lambda (i) (+ (% (+ i m) n) 1)) ilist))
     list))

  (define (iter-rotate m datalist)
    (if (= m 0)
    '()
    (cons (rotate m n datalist) (iter-rotate (- m 1) datalist))))
  (iter-rotate n (first n)))
(display (kirkman-2 6))
(newline)

DouKaku?

総当たり戦の日程作成

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq