Tutti i possibili abbinamenti di tornei in modo tale da non ottenere coppie dallo stesso gruppo.
Ho pensato a questo problema per un po ', ma non ho idea di come affrontarlo.
Hai 8 gruppi, con 4 dei gruppi con 6 persone e il resto dei 4 gruppi con 3 persone. Quindi hai 36 persone in totale.
Ora vogliamo scegliere 18 coppie da 36 persone per formare un torneo.
Credo che ci siano $\frac{36!}{18! 2^{18}}$(Non capisco davvero come ottenere questo numero) come si può vedere qui: Numero di modi in cui puoi formare coppie con un gruppo di persone quando certe persone non possono essere accoppiate tra loro.
Ora, voglio che gli abbinamenti siano tali che nessuna persona dello stesso gruppo giochi l'una contro l'altra. Quanti abbinamenti possibili esistono sotto questo vincolo?
Questa è una domanda molto simile: sorteggio quarti di finale di UEFA Champions League 2018 - accoppiamento di squadre della stessa nazione
Tuttavia, non credo che l'approccio lì funzionerebbe.
Grazie!
EDIT: La forma più generale di questa domanda sarebbe quella di far variare il numero di gruppi e il numero di persone in ciascun gruppo e di trovare la formula per questo. Ora mi chiedo se esiste una formula del genere. Ad esempio, cosa succede se hai 11 gruppi e 4 di loro hanno 5 persone, 5 di loro hanno 4 persone e 2 di loro hanno 12 persone.
MODIFICARE:
Ho eseguito alcune simulazioni, continuo a ottenere circa 0,11 invece dello 0,245 di Henry. Ecco il mio codice.
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
E alcuni risultati ottengo:
Per 3 gruppi di 4 persone, 2 persone e 2 persone, ottengo 24 su 105
Per 3 gruppi di 3 persone, 3 persone e 2 persone, ottengo 36 su 105
Per 5 gruppi di 2 persone, 2 persone, 2 persone, 1 persona e 1 persona, ottengo 68 su 105.
Risposte
Il numero è 24855678464505984000.
Supponiamo di averlo fatto $k$ diversi gruppi, di dimensioni $N_1, N_2 ... N_k$. Definire$F(N_1, N_2, ... N_k)$essere il numero di possibili tornei. Quindi la risposta al tuo problema particolare è$F(3, 3, 3, 3, 6, 6, 6, 6)$.
Come calcolare $F$? Possiamo inventare una relazione di ricorrenza e, auspicabilmente, un computer dovrebbe calcolarla. Ecco la relazione di ricorrenza:
$$ 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'idea è che scegliamo una coppia (da gruppi diversi), quindi scopriamo il sottoproblema con quella coppia rimossa. Il fattore$2 / \sum_l N_l$ deriva dal fatto che possiamo scegliere una qualsiasi delle coppie come prima, il che porterebbe a un conteggio eccessivo senza dividere per il numero di coppie.
Per i casi base, abbiamo $F(0, 0, \dots 0) = 1$, e $F=0$ se uno dei suoi argomenti è 0.
Ho usato il codice seguente, che richiede circa un minuto per essere eseguito.
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))
Questo stampa 24855678464505984000. Ciò significa che la probabilità di trovare un torneo di successo (ovvero nessuna coppia dello stesso gruppo) campionando casualmente da tutti gli accoppiamenti possibili è di circa 0,11, come previsto.