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

> karkman(6)
[[1]]
[1] "1-2" "1-3" "1-4" "1-5" "1-6"

[[2]]
[1] "2-3" "2-4" "2-5" "2-6"

[[3]]
[1] "3-4" "3-5" "3-6"

[[4]]
[1] "4-5" "4-6"

[[5]]
[1] "5-6"

> karkman(4)
[[1]]
[1] "1-2" "1-3" "1-4"

[[2]]
[1] "2-3" "2-4"

[[3]]
[1] "3-4"

>

1	karkman<-function(y)mapply(function(x)(paste(x,(x+1):y,sep="-")), 1:(y-1))

出力結果を見ると、お題の意図とは違うような気がします（読み間違えてたらすみません）

Rらしさは全くありませんが、参考URLに記載されたアルゴリズムを素直に実装してみました。

kirkman <- function(n=6){
    l <- 2:n
    fold <- n/2

    for(i in 2:n){
        print(paste(c(1, l[c(2:fold)]), c(i, l[(n-1):(fold+1)])))
        l <- c(l[-1], l[1])
    }
}

リストでかえしただけが悪いんですかね?じゃあ追加しておきましょう。
> print.karkman(4)
1-2 
1-3 
1-4 
2-3 
2-4 
3-4 
> print.karkman(6)
1-2 
1-3 
1-4 
1-5 
1-6 
2-3 
2-4 
2-5 
2-6 
3-4 
3-5 
3-6 
4-5 
4-6 
5-6 
>

1	print.karkman<-function(x)for(i in karkman(x))for(j in i)cat(j,"\n")

DouKaku?

総当たり戦の日程作成

Posted feedbacks - R

Index

Feed

Other

Link

Pathtraq