การจับคู่ทัวร์นาเมนต์ที่เป็นไปได้ทั้งหมดจะทำให้คุณไม่มีคู่จากกลุ่มเดียวกัน
ฉันคิดเกี่ยวกับปัญหานี้มาระยะหนึ่งแล้ว แต่ฉันไม่รู้ว่าจะแก้ไขอย่างไร
คุณมี 8 กลุ่มโดย 4 กลุ่มมี 6 คนและ 4 กลุ่มที่เหลือมี 3 คน คุณมีทั้งหมด 36 คน
ตอนนี้เราต้องการเลือก 18 คู่จาก 36 คนเพื่อสร้างทัวร์นาเมนต์
ฉันเชื่อว่ามี $\frac{36!}{18! 2^{18}}$(ฉันไม่เข้าใจวิธีรับตัวเลขนี้จริงๆ) ดังที่เห็นได้ที่นี่: จำนวนวิธีที่คุณสามารถสร้างคู่กับกลุ่มคนเมื่อบางคนไม่สามารถจับคู่กันได้
ตอนนี้ฉันต้องการให้การจับคู่เป็นแบบที่ไม่มีคนจากกลุ่มเดียวกันเล่นกันเอง มีการจับคู่ที่เป็นไปได้กี่รายการภายใต้ข้อ จำกัด นี้?
นี่เป็นคำถามที่คล้ายกันมาก: การจับสลากยูฟ่าแชมเปียนส์ลีกรอบก่อนรองชนะเลิศปี 2018 - การจับคู่ทีมในประเทศเดียวกัน
อย่างไรก็ตามฉันไม่คิดว่าวิธีนี้จะได้ผล
ขอบคุณ!
แก้ไข: รูปแบบทั่วไปที่สุดของคำถามนี้คือการปล่อยให้จำนวนกลุ่มและจำนวนคนในแต่ละกลุ่มแตกต่างกันไปและหาสูตรสำหรับสิ่งนี้ ตอนนี้ฉันสงสัยว่ามีสูตรดังกล่าวอยู่หรือเปล่า ตัวอย่างเช่นถ้าคุณมี 11 กลุ่มและ 4 ในนั้นมี 5 คน 5 คนมี 4 คนและ 2 ในนั้นมี 12 คน
แก้ไข:
ฉันใช้การจำลองสถานการณ์ฉันได้ประมาณ 0.11 แทนที่จะเป็น 0.245 ของเฮนรี่ นี่คือรหัสของฉัน
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
และผลลัพธ์บางอย่างที่ฉันได้รับ:
สำหรับกลุ่ม 3 คน 4 คน 2 คนและ 2 คนฉันได้ 24 จาก 105 คน
สำหรับกลุ่ม 3 คน 3 คน 3 คนและ 2 คนฉันได้ 36 จาก 105 คน
สำหรับกลุ่ม 5 คน 2 คน 2 คน 1 คนและ 1 คนฉันได้ 68 จาก 105 คน
คำตอบ
หมายเลขคือ 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
ฉันใช้รหัสต่อไปนี้ซึ่งใช้เวลาประมาณหนึ่งนาทีในการรัน
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 ตามที่คาดไว้