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

あまり奇麗ではありませんが。

scheduling 6

# => [[1, 2], [6, 3], [5, 4]]
     [[1, 6], [5, 2], [4, 3]]
     [[1, 5], [4, 6], [3, 2]]
     [[1, 4], [3, 5], [2, 6]]
     [[1, 3], [2, 4], [6, 5]]

def scheduling(n)
  teams = [1] + (2..n).to_a.reverse
  half = n / 2
  (n - 1).times do
    p teams[0, half].zip teams[half, half].reverse
    teams = [1] + teams[2..-1].push(teams[1])
  end
end

一応、全ての可能性を探っているはず・・・
（結果表示は数だけ）
だけど、あんまり自信無し・・・（^^;）

ポイントは、「とにかく、injectを使ってみる」です。(^^

see: 順列の生成とList内包表記

def allsche(num)
  teams = (1..num).to_a
  headteam = teams[0,1]
  anotherteams = teams[1..-1]
  anotherteams.permutations.inject([]) {|result, ar|
    result << match_sche(headteam, ar)
  }
end

def match_sche(headteam , anotherteams)
  (1..anotherteams.length).inject([]) {|result, notuse|
    teams = headteam + anotherteams
    anotherteams = anotherteams.rotate
    spar = teams.split(teams.length / 2)
    result << spar[0].zip(spar[1].reverse)
  }
end

class Array
  def permutations
    if empty?
      [[]]
    else
      inject([]) {|result, item|
        minusone = self - [item]
        subperms = minusone.permutations
        newperms = subperms.map{|pm| [item] + pm }
        result + newperms
      }
    end
  end

  def rotate(n = 1)
    (1..n).inject(self.dup) {|result, notuse| [result.pop] + result }
  end
  
  def split(n)
    [self[0,n], self[n..-1]]
  end
end

# MAIN
require 'pp'
allsche =  allsche(ARGV[0].to_i)
puts allsche.length
pp allsche[0]

DouKaku?

総当たり戦の日程作成

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq