総当たり戦の日程作成 in Scala 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: カークマンの組分け

とりあえず。

def cycleS[T](a:Seq[T],i:int,j:int) = Stream.const(a).flatMap(v=>v).slice(i,j)
def sportsScheduling(n:int) = {
  List((1 to n)).map{ lst => 
    val x = n/2-1;val root = lst(0)
    (0 to n-2).map{i =>
      println(i)
      val c = cycleS(cycleS(lst, 1, n), i+x+1, i+x+n)
      (root, c(x))::((1 to x).map{j => (c(x+j), c(x-j))}.toList)
    }.toList
  }.toList
}

すみません、いらないprintlnが入ってました。

def cycleS[T](a:Seq[T],i:int,j:int) = Stream.const(a).flatMap(v=>v).slice(i,j)
def sportsScheduling(n:int) = {
  List((1 to n)).map{ lst => 
    val x = n/2-1;val root = lst(0)
    (0 to n-2).map{i =>
      val c = cycleS(cycleS(lst, 1, n), i+x+1, i+x+n)
      (root, c(x))::((1 to x).map{j => (c(x+j), c(x-j))}.toList)
    }.toList
  }.toList
}

Listを引数にとるバージョン
全組み合わせ出力への１歩
（・・・しかし、型がList[List[(T,T)]]とかなると、やっぱりちょっと見難いなぁ）

object sche {
  def match_sche[T](t:List[T]) = match_sche_loop(List(), t)
  def match_sche_loop[T](acc:List[List[(T,T)]], l:List[T]):List[List[(T,T)]] = {
    if (acc.length == (l.length-1)) acc
    else {
      val sp     = l.splitAt(l.length/2)
      val newacc = sp._1.zip(sp._2.reverse) :: acc
      val newl   = l.head :: l.tail.tail ::: List(l.tail.head)
      match_sche_loop(newacc, newl)
    }
  }

  def main(args: Array[String]) {
    val n = args(0).toInt
    match_sche((1 to n).toList).foreach {println(_)}
  }
}

DouKaku?

総当たり戦の日程作成

Posted feedbacks - Scala

Index

Feed

Other

Link

Pathtraq