Semua kemungkinan pemasangan turnamen sedemikian rupa sehingga Anda tidak mendapatkan pasangan dari grup yang sama.

Jan 03 2021

Saya memikirkan masalah ini sebentar, tetapi saya tidak tahu bagaimana mendekatinya.

Anda memiliki 8 grup, dengan 4 grup beranggotakan 6 orang dan sisanya 4 grup beranggotakan 3 orang. Jadi Anda memiliki total 36 orang.

Sekarang kami ingin memilih 18 pasang dari 36 orang untuk membentuk sebuah turnamen.

Saya yakin ada $\frac{36!}{18! 2^{18}}$(Saya tidak begitu mengerti bagaimana cara mendapatkan nomor ini) seperti yang dapat dilihat di sini: Jumlah cara Anda dapat membentuk pasangan dengan sekelompok orang ketika orang tertentu tidak dapat dipasangkan satu sama lain.

Sekarang, saya ingin pasangan dibuat sedemikian rupa sehingga tidak ada orang dari grup yang sama yang bermain melawan satu sama lain. Berapa banyak kemungkinan pasangan yang ada di bawah batasan ini?

Ini adalah pertanyaan yang sangat mirip: undian perempatfinal Liga Champions UEFA 2018 - pasangan tim negara yang sama

Namun, saya tidak berpikir pendekatan di sana akan berhasil.

Terima kasih!

EDIT: Bentuk paling umum dari pertanyaan ini adalah membiarkan jumlah kelompok dan jumlah orang dalam setiap kelompok berbeda, dan menemukan rumus untuk ini. Saya sekarang bertanya-tanya apakah rumus seperti itu ada. Jadi misalnya, bagaimana jika Anda memiliki 11 kelompok, dan 4 di antaranya ada 5 orang, 5 di antaranya ada 4 orang, dan 2 di antaranya ada 12 orang.

EDIT:

Saya menjalankan beberapa simulasi, saya terus mendapatkan sekitar 0,11 bukannya 0,245 Henry. Ini kode saya.

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

Dan beberapa hasil yang saya dapatkan:

Untuk 3 grup yang terdiri dari 4 orang, 2 orang, dan 2 orang, saya dapatkan 24 dari 105

Untuk 3 kelompok yang terdiri dari 3 orang, 3 orang dan 2 orang, saya dapatkan 36 dari 105

Untuk 5 grup 2 orang, 2 orang, 2 orang, 1 orang dan 1 orang saya dapatkan 68 dari 105.

Jawaban

2 RickyTensor Jan 05 2021 at 12:47

Nomornya adalah 24855678464505984000.

Misalkan kita punya $k$ kelompok yang berbeda, ukuran $N_1, N_2 ... N_k$. Menetapkan$F(N_1, N_2, ... N_k)$menjadi jumlah turnamen yang memungkinkan. Jadi jawaban untuk masalah khusus Anda adalah$F(3, 3, 3, 3, 6, 6, 6, 6)$.

Bagaimana cara menghitung $F$? Kami dapat membuat relasi berulang, dan semoga komputer dapat menghitungnya. Berikut hubungan perulangannya:

$$ 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) $$

Idenya adalah kita memilih pasangan (dari kelompok yang berbeda), kemudian mencari tahu subproblem dengan pasangan tersebut dihapus. Faktor$2 / \sum_l N_l$ berasal dari fakta bahwa kita dapat memilih salah satu pasangan untuk menjadi yang pertama, yang akan menyebabkan penghitungan berlebih tanpa membaginya dengan jumlah pasangan.

Untuk kasus dasar, kami punya $F(0, 0, \dots 0) = 1$, dan $F=0$ jika salah satu argumennya adalah 0.

Saya menggunakan kode berikut, yang membutuhkan waktu sekitar satu menit untuk dijalankan.

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))

Ini mencetak 24855678464505984000. Itu berarti probabilitas menemukan turnamen yang sukses (artinya tidak ada pasangan dari grup yang sama) dengan pengambilan sampel secara acak dari semua kemungkinan pasangan adalah sekitar 0,11, seperti yang diharapkan.