Tous les appariements de tournois possibles de sorte que vous n'obteniez aucune paire du même groupe.
J'ai réfléchi à ce problème pendant un moment, mais je ne sais pas comment l'aborder.
Vous avez 8 groupes, 4 des groupes ayant 6 personnes et le reste des 4 groupes ayant 3 personnes. Vous avez donc 36 personnes au total.
Maintenant, nous voulons choisir 18 paires de 36 personnes pour former un tournoi.
Je crois qu'il y a $\frac{36!}{18! 2^{18}}$(Je ne comprends pas vraiment comment obtenir ce nombre) comme on peut le voir ici: Nombre de façons dont vous pouvez former des paires avec un groupe de personnes lorsque certaines personnes ne peuvent pas être jumelées les unes aux autres.
Maintenant, je veux que les paires soient telles qu'aucune personne du même groupe ne joue les unes contre les autres. Combien d'appariements possibles existent sous cette contrainte?
C'est une question très similaire: tirage au sort des quarts de finale de l'UEFA Champions League 2018 - appariement des mêmes équipes nationales
Cependant, je ne pense pas que cette approche fonctionnerait.
Merci!
EDIT: La forme la plus générale de cette question serait de laisser le nombre de groupes et le nombre de personnes dans chaque groupe varier, et de trouver la formule pour cela. Je me demande maintenant si une telle formule existe. Par exemple, que se passe-t-il si vous avez 11 groupes, et 4 d'entre eux ont 5 personnes, 5 d'entre eux ont 4 personnes et 2 d'entre eux ont 12 personnes.
ÉDITER:
J'ai exécuté une simulation, je continue à obtenir environ 0,11 au lieu de 0,245 de Henry. Voici mon 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
Et quelques résultats que j'obtiens:
Pour 3 groupes de 4 personnes, 2 personnes et 2 personnes, j'obtiens 24 sur 105
Pour 3 groupes de 3 personnes, 3 personnes et 2 personnes, j'obtiens 36 sur 105
Pour 5 groupes de 2 personnes, 2 personnes, 2 personnes, 1 personne et 1 personne, j'obtiens 68 sur 105.
Réponses
Le numéro est 24855678464505984000.
Supposons que nous ayons $k$ différents groupes, de tailles $N_1, N_2 ... N_k$. Définir$F(N_1, N_2, ... N_k)$être le nombre de tournois possibles. La réponse à votre problème particulier est donc$F(3, 3, 3, 3, 6, 6, 6, 6)$.
Comment calculer $F$? Nous pouvons trouver une relation de récurrence et, espérons-le, un ordinateur devrait la calculer. Voici la relation de récurrence:
$$ 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) $$
L'idée est que nous choisissons une paire (parmi différents groupes), puis que nous déterminons le sous-problème avec cette paire supprimée. Le facteur$2 / \sum_l N_l$ vient du fait que l'on peut choisir n'importe laquelle des paires pour être la première, ce qui conduirait à un sur-comptage sans diviser par le nombre de paires.
Pour les cas de base, nous avons $F(0, 0, \dots 0) = 1$, et $F=0$ si l'un de ses arguments vaut 0.
J'ai utilisé le code suivant, qui prend environ une minute à exécuter.
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))
Cela imprime 24855678464505984000. Cela signifie que la probabilité de trouver un tournoi réussi (ce qui signifie qu'aucune paire du même groupe) par échantillonnage aléatoire de toutes les paires possibles est d'environ 0,11, comme prévu.