Wszystkie możliwe parowania w turniejach, w których nie ma pary z tej samej grupy.
Przez chwilę myślałem o tym problemie, ale nie mam pojęcia, jak do niego podejść.
Masz 8 grup, przy czym 4 z grup mają 6 osób, a reszta 4 grup ma 3 osoby. W sumie masz 36 osób.
Teraz chcemy wybrać 18 par z 36 osób, aby utworzyć turniej.
Myślę, że są $\frac{36!}{18! 2^{18}}$(Jednak nie bardzo rozumiem, jak uzyskać tę liczbę), jak widać tutaj: Liczba sposobów tworzenia par z grupą osób, gdy niektórych osób nie można ze sobą sparować.
Teraz chcę, aby pary były takie, aby żadna osoba z tej samej grupy nie grała przeciwko sobie. Ile możliwych par istnieje pod tym ograniczeniem?
To bardzo podobne pytanie: losowanie ćwierćfinałów Ligi Mistrzów UEFA 2018 - parowanie tych samych drużyn krajowych
Jednak nie sądzę, żeby to podejście zadziałało.
Dzięki!
EDYCJA: Najbardziej ogólną formą tego pytania byłoby pozwolenie na zmianę liczby grup i liczby osób w każdej grupie i znalezienie wzoru na to. Zastanawiam się teraz, czy taka formuła istnieje. Na przykład, co jeśli masz 11 grup, a 4 z nich mają 5 osób, 5 z nich ma 4 osoby, a 2 z nich mają 12 osób.
EDYTOWAĆ:
Uruchomiłem symulację, ciągle otrzymuję około 0,11 zamiast 0,245 Henry'ego. Oto mój kod.
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
I niektóre wyniki, które otrzymuję:
Dla 3 grup po 4 osoby, 2 osoby i 2 osoby otrzymuję 24 na 105
Dla 3 grup po 3 osoby, 3 osoby i 2 osoby otrzymuję 36 na 105
Dla 5 grup po 2 osoby, 2 osoby, 2 osoby, 1 osoba i 1 osoba otrzymuję 68 na 105.
Odpowiedzi
Numer to 24855678464505984000.
Załóżmy, że mamy $k$ różne grupy, wielkości $N_1, N_2 ... N_k$. Definiować$F(N_1, N_2, ... N_k)$być liczbą możliwych turniejów. Więc odpowiedź na twój konkretny problem brzmi$F(3, 3, 3, 3, 6, 6, 6, 6)$.
Jak obliczyć $F$? Możemy wymyślić relację powtarzania i miejmy nadzieję, że komputer powinien ją obliczyć. Oto relacja powtarzania:
$$ 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) $$
Chodzi o to, że wybieramy parę (z różnych grup), a następnie ustalamy podproblem z usuniętą parą. Czynnik$2 / \sum_l N_l$ wynika z tego, że możemy wybrać dowolną z par jako pierwszą, co doprowadziłoby do przeliczenia bez dzielenia przez liczbę par.
W przypadku przypadków podstawowych mamy $F(0, 0, \dots 0) = 1$, i $F=0$ jeśli którykolwiek z jego argumentów ma wartość 0.
Użyłem następującego kodu, którego uruchomienie zajmuje około minuty.
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))
To wypisuje 24855678464505984000. Oznacza to, że prawdopodobieństwo znalezienia udanego turnieju (co oznacza brak par z tej samej grupy) przez losowe próbkowanie ze wszystkich możliwych par wynosi około 0,11, zgodnie z oczekiwaniami.