同じグループからペアを獲得しないような、可能なすべてのトーナメントペアリング。
しばらく考えていたのですが、どうやって取り組むのかわかりません。
8つのグループがあり、そのうち4つのグループは6人で、残りの4つのグループは3人です。つまり、合計36人です。
今度は36人から18ペアを選んでトーナメントを作りたいと思います。
あると思います $\frac{36!}{18! 2^{18}}$（私はこの番号を取得する方法を本当に理解していません）ここに見られるように：特定の人々が互いにペアになることができないときに人々のグループとペアを形成することができる方法の数。
さて、同じグループの人がお互いに対戦しないようなペアリングをしたいと思います。この制約の下で可能なペアリングはいくつありますか？
これは非常によく似た質問です：UEFAチャンピオンズリーグ準々決勝2018抽選-同じ国のチームのペアリング
しかし、そこでのアプローチはうまくいかないと思います。
ありがとう！
編集：この質問の最も一般的な形式は、グループの数と各グループの人数を変化させ、このための公式を見つけることです。私は今、そのような公式が存在するかどうか疑問に思っています。たとえば、11のグループがあり、そのうちの4つが5人、5つが4人、2つが12人の場合はどうでしょうか。
編集：
シミュレーションを実行しましたが、ヘンリーの0.245ではなく約0.11を取得し続けています。これが私のコードです。
team_list = c(rep(1:6, 4), rep(1:3,4))
for (i in 1:6){
team_list[i] = paste("A", team_list[i], sep = "")
}
for (i in 7:12){
team_list[i] = paste("B", team_list[i], sep = "")
}
for (i in 13:18){
team_list[i] = paste("C", team_list[i], sep = "")
}
for (i in 19:24){
team_list[i] = paste("D", team_list[i], sep = "")
}
for (i in 25:27){
team_list[i] = paste("E", team_list[i], sep = "")
}
for (i in 28:30){
team_list[i] = paste("F", team_list[i], sep = "")
}
for (i in 31:33){
team_list[i] = paste("G", team_list[i], sep = "")
}
for (i in 34:36){
team_list[i] = paste("H", team_list[i], sep = "")
}
check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}
count = 0
for (i in 1:10000){
x = sample(team_list, size = 36)
if (!check_pair(x)){
count = count+1
}
}
count/10000
team_list = c("A1", "A2", "B1", "B2", "C1", "C2")
pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}
pair_combn(team_list)
check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}
count = 0
for (i in 1:10000){
x = sample(team_list, size = 6)
if (!check_pair(x)){
count = count+1
}
}
count/10000
team_list = c("A1", "A2", "B1", "B2", "C1", "D1")
pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}
pair_combn(team_list)
check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}
count = 0
for (i in 1:10000){
x = sample(team_list, size = 6)
if (!check_pair(x)){
count = count+1
}
}
count/10000
z = pair_combn(team_list)
team_list = c("A1", "A2", "B1", "B2", "C1", "D1", "E1", "E2")
pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}
combination = pair_combn(team_list)
check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}
count = 0
for (i in 1:105){
to_check = as.vector(unlist(combination[[i]]))
if (!check_pair(to_check)){
count = count+1
}
}
print (count)
count = 0
for (i in 1:10000){
x = sample(team_list, size = 8)
if (!check_pair(x)){
count = count+1
}
}
count/10000
team_list = c("A1", "A2", "A3", "A4", "B1", "B2", "C1", "C2")
pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}
combination = pair_combn(team_list)
check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}
count = 0
for (i in 1:105){
to_check = as.vector(unlist(combination[[i]]))
if (!check_pair(to_check)){
count = count+1
}
}
print (count)
count = 0
for (i in 1:10000){
x = sample(team_list, size = 8)
if (!check_pair(x)){
count = count+1
}
}
count/10000
team_list = c("A1", "A2", "A3", "B1", "B2", "B3", "C1", "C2")
pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}
combination = pair_combn(team_list)
check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}
count = 0
for (i in 1:105){
to_check = as.vector(unlist(combination[[i]]))
if (!check_pair(to_check)){
count = count+1
}
}
print (count)
count = 0
for (i in 1:10000){
x = sample(team_list, size = 8)
if (!check_pair(x)){
count = count+1
}
}
count/10000
そして私が得るいくつかの結果：
4人、2人、2人の3グループの場合、105人中24人になります
3人3人3人2人で105人中36人
2人、2人、2人、1人、1人の5グループの場合、105人中68人になります。
回答
番号は24855678464505984000です。
私たちが持っているとしましょう $k$ サイズの異なるグループ $N_1, N_2 ... N_k$。定義する$F(N_1, N_2, ... N_k)$可能なトーナメントの数になります。だからあなたの特定の問題への答えは$F(3, 3, 3, 3, 6, 6, 6, 6)$。
計算方法 $F$？漸化式を考え出すことができます。うまくいけば、コンピューターがそれを計算する必要があります。漸化式は次のとおりです。
$$ F(N_1...N_k) = \frac{2}{\sum_l N_l}\sum_i\sum_{j < i} N_j \times N_i \times F(N_1, N_2\dots N_j-1 \dots N_i-1 \dots N_k) $$
アイデアは、（異なるグループから）ペアを選択し、そのペアを削除してサブ問題を把握することです。要因$2 / \sum_l N_l$ ペアのいずれかを最初のペアとして選択できるため、ペアの数で除算せずに過大カウントにつながる可能性があります。
基本ケースについては、 $F(0, 0, \dots 0) = 1$、および $F=0$ その引数のいずれかが0の場合。
次のコードを使用しましたが、実行には約1分かかります。
from functools import lru_cache
@lru_cache(maxsize = 1000000)
def F(M, ntup, k):
if M < 0: return 0
for n in ntup:
if n < 0: return 0
if M == 0:
return 1
ans = 0
for i in range(1, k):
for j in range(0, i):
ans += ntup[i] * ntup[j] * F(M-2, ntup[:j] + (ntup[j]-1,) + ntup[j+1:i] + (ntup[i]-1,) + (ntup[i+1:] if i+1 < k else ()), k)
return (2 * ans) // M
print(F(36, (3, 3, 3, 3, 6, 6, 6, 6), 8))
これは24855678464505984000を出力します。つまり、すべての可能なペアからランダムにサンプリングすることによって、成功したトーナメント（同じグループからのペアがないことを意味します）を見つける確率は、予想どおり約0.11です。