Algoritmo e struttura dati per abbinare gruppi di utenti (1-5 ciascuno) in 2 gruppi bilanciati di 5 utenti

La prima cosa è conoscere le partizioni del numero 5 (la dimensione della squadra che si desidera assemblare). Esistono degli algoritmi per generare le partizioni di un numero, ma poiché il numero è piccolo e fisso non è necessario preoccuparsene. Le partizioni di 5 sono: {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1), {2,1,1,1} e { 1,1,1,1,1}.

Crea 5 elenchi di lobby (L1, L2, L3, L4, L5). Uno per ogni dimensione della lobby. Ogni elemento conterrà: 1) l'id della lobby 2) il tempo in coda 3) la somma dei ranghi dei giocatori che compongono la lobby L1 è l'elenco di tutte le lobby di dimensione 1, L2 è l'elenco di tutte le lobby di dimensione 2 e così via.

Ora fai una lista di tutte le possibili squadre di 5 persone che puoi assemblare dalle 5 liste di lobby. Per costruire quell'elenco, fai scorrere in loop gli elenchi L1, ... L5 in base alle partizioni di 5.

team {
    int partition_type;
    int lobby_index[5]; //each lobby_index value will mean a different thing depending on the value of partition_type
}

team_index = 0

//partition case 0: {5}
for (i5=0; i5<n5; i5++) do
    //in the case of partition_type==0, only the first index is used and it is an index in the list of lobbies of size 5
    Team[team_index++] = new team(partition_type = 0, lobby_index[0] = i5)
end

//partition case 1: {4,1}
for (i4=0; i4<n4; i4++) do
    for (i1=0; i1<n1; i1++) do
        //in the case of partition_type==1, the first index is an index in the list of lobbies of size 4 and the second is an index in the list of size 1
        Team[team_index++] = new team(partition_type = 1, lobby_index[0] = i4, lobby_index[1] = i1)
    end
end

//partition case 2: {3,2}
for (i3=0; i3<n3; i3++) do
    for (i2=0; i2<n2; i2++) do
        Team[team_index++] = new team(partition_type = 2, lobby_index[0] = i3, lobby_index[1] = i2)
    end
end

//partition case 3: {3,1,1}
for (i3=0; i3<n3; i3++) do
    for (i1a=0; i1a<n1-1; i1a++) do // 0 <= i1a < i1b < n1
        for (i1b=i1a+1; i1b<n1; i1b++) do
            Team[team_index++] = new team(partition_type = 3, lobby_index[0] = i3, lobby_index[1] = i1a, lobby_index[2] = i1b)
        end
    end
end

//partition case 4: {2,2,1)
for (i2a=0; i2a<n2-1; i2a++) do  // 0 <= i2a < i2b < n2
    for (i2b=i2a+1; i2b<n2; i2b++) do
        for (i1=0; i1<n1; i1++) do
            Team[team_index++] = new team(partition_type = 4, lobby_index[0] = i2a, lobby_index[1] = i2b, lobby_index[2] = i1)
        end
    end
end

//partition case 5: {2,1,1,1}
for (i2=0; i2<n2; i2++) do
    for (i1a=0; i1a<n1-2; i1a++) do  // 0 <= i1a < i1b < i1c < n1
        for (i1b=i1a+1; i1b<n1-1; i1b++) do
            for (i1c=i1b+1; i1c<n1; i1c++) do
                Team[team_index++] = new team(partition_type = 5,     lobby_index[0] = i2, lobby_index[1] = i1a, lobby_index[2] = i1b, lobby_index[3] = i1c)
            end
        end
    end
end

//partition case 6: {1,1,1,1,1}
for (i1a=0; i1a<n1-4; i1a++) do  // 0 <= i1a < i1b < i1c < i1d < n1
    for (i1b=i1a+1; i1b<n1-3; i1b++) do
        for (i1c=i1b+1; i1c<n1-2; i1c++) do
            for (i1d=i1c+1; i1d<n1-1; i1d++) do
                for (i1e=i1d+1; i1e<n1; i1e++) do
                    Team[team_index++] = new team(partition_type = 6, lobby_index[0] = i1a, lobby_index[1] = i1b, lobby_index[2] = i1c, lobby_index[3] = i1d, lobby_index[4] = i1e))
            end
        end
    end
end

Per calcolare il grado di una squadra [30] (mostrando solo un caso):

if Team[30].partition_type==2 then
    i3 = Team[30].lobby_index[0]
    i2 = Team[30].lobby_index[1]
    rank = ( (L3[i3].rank) + (L2[i2].rank) ) / 5
end

Hai 2 copie di T (o almeno assicurati di poterlo attraversare in 2 modi diversi). Uno ordinato per il rango medio di quella squadra e l'altra copia ordinata per il tempo medio in coda.

Ora attraversa la lista T ordinata in base al tempo di coda da più alto a più basso. Il primo elemento è quello che ha la priorità di trovare prima un gioco perché i suoi membri stanno aspettando più a lungo in media. Controlla la media dei ranghi di questa squadra. Ora usa il valore di classifica che hai trovato per determinare tutte le squadre che sono +/- 1.5 dal suo valore. Questo è fatto facilmente usando la lista delle squadre T copia ordinata per classifica. Ora devi solo controllare se nessuna delle squadre nella gamma di classifica non include alcuna lobby della squadra attuale (poiché una lobby non può essere in entrambe le squadre).

Se c'è una squadra del genere, hai appena trovato un gioco (se ci sono più di un prelievo e uno con il tempo di coda più alto). Rimuovi tutte le lobby coinvolte dai loro elenchi e ricalcola di nuovo tutte le squadre. In caso contrario, ottenere la squadra successiva nell'elenco ordinato per tempo di attesa e riprovare. Una volta attraversato tutto il tempo di attesa della coda, attendi che l'elenco delle code cambi e faccia di nuovo tutto.

1. Calcola il punteggio totale di tutti i giocatori in una singola lobby.

2. Corrisponde a un'altra lobby basata su questo. (+ - 1.5 intervallo più o meno)

Non è così semplice?