Alle möglichen Turnierpaarungen, sodass Sie kein Paar aus derselben Gruppe erhalten.

Jan 03 2021

Ich habe eine Weile über dieses Problem nachgedacht, aber ich habe keine Ahnung, wie ich es angehen soll.

Sie haben 8 Gruppen, wobei 4 der Gruppen 6 Personen und die restlichen 4 Gruppen 3 Personen haben. Sie haben also insgesamt 36 Personen.

Jetzt wollen wir 18 Paare aus 36 Personen auswählen, um ein Turnier zu bilden.

Ich glaube es gibt $\frac{36!}{18! 2^{18}}$(Ich verstehe allerdings nicht wirklich, wie man diese Nummer erhält) wie hier zu sehen ist: Anzahl der Möglichkeiten, wie Sie mit einer Gruppe von Personen Paare bilden können, wenn bestimmte Personen nicht miteinander gepaart werden können.

Jetzt möchte ich, dass die Paarungen so sind, dass keine Personen derselben Gruppe gegeneinander spielen. Wie viele mögliche Paarungen existieren unter dieser Einschränkung?

Dies ist eine sehr ähnliche Frage: Unentschieden im Viertelfinale der UEFA Champions League 2018 - Paarung derselben Landesteams

Ich denke jedoch nicht, dass der Ansatz dort funktionieren würde.

Vielen Dank!

EDIT: Die allgemeinste Form dieser Frage wäre, die Anzahl der Gruppen und die Anzahl der Personen in jeder Gruppe variieren zu lassen und die Formel dafür zu finden. Ich frage mich jetzt, ob es eine solche Formel gibt. Was ist zum Beispiel, wenn Sie 11 Gruppen haben und 4 von ihnen 5 Personen haben, 5 von ihnen 4 Personen haben und 2 von ihnen 12 Personen haben.

BEARBEITEN:

Ich habe eine Simulation durchgeführt, ich bekomme immer ungefähr 0,11 anstelle von Henrys 0,245. Hier ist mein Code.

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

Und einige Ergebnisse bekomme ich:

Für 3 Gruppen von 4 Personen, 2 Personen und 2 Personen bekomme ich 24 von 105

Für 3 Gruppen von 3 Personen, 3 Personen und 2 Personen bekomme ich 36 von 105

Für 5 Gruppen von 2 Personen, 2 Personen, 2 Personen, 1 Person und 1 Person bekomme ich 68 von 105.

Antworten

2 RickyTensor Jan 05 2021 at 12:47

Die Nummer lautet 24855678464505984000.

Angenommen, wir haben $k$ verschiedene Gruppen von Größen $N_1, N_2 ... N_k$. Definieren$F(N_1, N_2, ... N_k)$die Anzahl der möglichen Turniere sein. Die Antwort auf Ihr spezielles Problem lautet also$F(3, 3, 3, 3, 6, 6, 6, 6)$.

Wie zu berechnen $F$? Wir können eine Wiederholungsrelation entwickeln, und hoffentlich sollte ein Computer sie berechnen. Hier ist die Wiederholungsrelation:

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

Die Idee ist, dass wir ein Paar (aus verschiedenen Gruppen) auswählen und dann das Teilproblem herausfinden, bei dem dieses Paar entfernt wurde. Der Faktor$2 / \sum_l N_l$ kommt von der Tatsache, dass wir jedes der Paare als das erste auswählen können, was zu einer Überzählung führen würde, ohne durch die Anzahl der Paare zu dividieren.

Für die Basisfälle haben wir $F(0, 0, \dots 0) = 1$, und $F=0$ wenn eines seiner Argumente 0 ist.

Ich habe den folgenden Code verwendet, dessen Ausführung ungefähr eine Minute dauert.

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

Dies gibt 24855678464505984000 aus. Dies bedeutet, dass die Wahrscheinlichkeit, ein erfolgreiches Turnier (dh keine Paare aus derselben Gruppe) durch zufällige Stichprobe aus allen möglichen Paarungen zu finden, erwartungsgemäß etwa 0,11 beträgt.