동일한 그룹에서 페어를 얻지 못하도록 가능한 모든 토너먼트 페어링.
이 문제에 대해 잠시 생각했지만 어떻게 접근해야할지 모르겠습니다.
당신은 8 개의 그룹이 있는데, 4 개 그룹은 6 명이고 나머지 4 개 그룹은 3 명입니다. 총 36 명이 있습니다.
이제 우리는 토너먼트를 구성하기 위해 36 명 중 18 쌍을 선택하려고합니다.
나는 있다고 믿는다 $\frac{36!}{18! 2^{18}}$(그래도이 번호를 얻는 방법을 이해하지 못합니다) 여기에서 볼 수 있듯이 특정 사람들이 서로 짝을 이룰 수 없을 때 사람들 그룹과 짝을 이룰 수있는 방법의 수입니다.
이제 나는 같은 그룹의 사람들이 서로 대결하지 않도록 페어링을 원합니다. 이 제약 조건에서 가능한 페어링은 몇 개입니까?
이것은 매우 유사한 질문입니다. UEFA 챔피언스 리그 2018 준준결승 무승부-같은 국가 팀의 짝짓기
그러나 나는 거기의 접근 방식이 효과가 있다고 생각하지 않습니다.
감사!
편집 :이 질문의 가장 일반적인 형태는 각 그룹의 그룹 수와 사람 수를 다양하게하고 이에 대한 공식을 찾는 것입니다. 나는 지금 그러한 공식이 존재하는지 궁금합니다. 예를 들어 11 개의 그룹이 있고 그 중 4 명이 5 명, 5 명에는 4 명, 2 명에는 12 명이 있다면 어떨까요?
편집하다:
몇 가지 시뮬레이션을 실행했는데 Henry의 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 인, 2 인 3 그룹의 경우 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입니다.