EXCEL: Ottimizazione gironi

[gudmund]

O esperti,
abbisogno di aiuto...
Devo gestire un torneo di calcio e mi trovo a combattere con la divisione delle squadre in gironi.
I gironi possono essere di 13, 14, 15 o 16 squadre, dando priorità ai gironi da 13 o 14. Al momento ho 111 iscritte, che con un rapido calcolo mentale (111/13=8 col resto di 7) dividerò ovviamente in 7 gironi da 14 e 1 da 13.
A mente è abbastanza semplice, andando per tentativi. A mente, appunto...
Ma se volessi chiederlo a Excel? In modo da avere un foglio pronto qualsiasi sia il numero di iscritti.
In realtà è diventata più una curiosità da appassionato di programmazione, che non una necessità pratica.
Mi va bene sia risolvere con formule che con VBA. Quello che mi interessa è come ragionare, da che base partire.
Grazie a chi vorrà perdere il proprio tempo per risolvere questo NON vitale quesito .
Ciao

[Flash30005]

La soluzione c'è
ma dovresti specificare come dovrebbero essere distribuiti gli iscritti nei vari gironi
Esiste una regola?
Sorteggio casuale?
Al variare del numro degli iscritti la macro dovrebbe provvedere ad assegnare il numero "ottimale" (un po' come il tuo ragionamento)?

(111/13=8 col resto di 7) dividerò ovviamente in 7 gironi da 14 e 1 da 13.

Perché potrei creare 13 gironi da 8 e uno da 7 iscritti
Quindi qual'è il numero minimo di iscritti nel girone?
Ad esempio se dovessero essere 101 iscritti come ti comporti?

Fai sapere
Ciao

[gudmund]

Grazie Flash,
Allora, i gironi devono essere compresi tra 13 e 16 squadre, non meno di 13 e non più di 16. Inoltre, siccome i gironi da 13 o da 14 durano due giornate di meno (una all'andata e una al ritorno) vorrei che ce ne fossero il più possibile. Basta, non ci sono altri limiti.
La distribuzione delle squadre nei gironi, invece, deve necessariamente essere fatta a mano, in quanto i criteri sono vari; primo tra tutti quello della distanza.

[gudmund]

Correzione: i gironi a 15 o 16 durano 4 giornate in più, 2 all'andata e 2 al ritorno. Pardon me

[Anthony47]

Io pero' non ho capito quale e' il problema inutile: individuare il numero di gironi, suddividere le squadre tra gli N gironi, preparare il calendario dei singoli gironi, . . . , ??

Ciao

[gudmund]

In realtà, Anthony, il quesito è più matematico che informatico. Si tratta di ottimizzare il numero di squadre per girone (che, ripeto, possono andare da 13 a 16). E' ovvio che le possibilità sono molte ma a me serve di comporre più gironi da 13 o 14 possibili.
Per esempio, con 101 squadre, preferisco avere 5 gironi da 14, 1 da 15 e 1 da 16, piuttosto che 4 da 14 e 3 da 15.
Solo questo.
In pratica Il titolo del post potrebbe diventare "ottimizzazione di insiemi".
Grazie

[Anthony47]

Ogni quesito e' innanzitutto una questione di logica.
La mia proposta e' di usare un po' di logica e un po' di forza bruta; usando questa macro:

Codice: Seleziona tutto

Sub Giropt()
Dim NumSq As Integer, BaseN As Integer, MaxC As Integer, FlaOk As Boolean
Dim J As Integer, K As Integer, L As Integer, M As Integer, CtComb As Integer
Range("J3:M500").ClearContents
Range("L3:M500").Value = 99
NumSq = Range("A2").Value
BaseN = 13
NumN = 4
MaxC = NumSq / BaseN
For J = MaxC To 0 Step -1
For K = MaxC To 0 Step -1
For L = MaxC To 0 Step -1
For M = MaxC To 0 Step -1
    If J * BaseN + K * (BaseN + 1) + L * (BaseN + 2) + M * (BaseN + 3) = NumSq Then
        Range("J3").Offset(CtComb, 0).Value = J
        Range("J3").Offset(CtComb, 1).Value = K
        Range("J3").Offset(CtComb, 2).Value = L
        Range("J3").Offset(CtComb, 3).Value = M
        If L + M = 0 Then FlaOk = True
        CtComb = CtComb + 1
    If FlaOk = True And CtComb > 30 Then Exit Sub
End If
Next M
Next L
Next K
Next J
End Sub


Inserendo il numero di squadre in A2 del foglio attivo ed eseguendo la macro verranno calcolate le possibili combinazioni, visualizzate in J3:M3 e sottostanti; ho immaginato di calcolare max 500 combinazioni (credo che sia una esagerazione), quindi la macro usa le celle J3:M500.
Comunque trovando una combinazione con solo 13 e 14, dopo 30 calcoli la macro viene terminata.

Per identificare le combinazioni ottimali ho usato sul range J3:M500 la formattazione condizionale con "la formula è" e formula

Codice: Seleziona tutto

=E(SOMMA($J3:$M3)>0;($L3+$M3)=MIN($L$3:$L$500+$M$3:$M$500))


Il risultato e' come quello dell' immagine:


Uploaded with ImageShack.us
Ho fatto anche un esercizio usando formule e "Ricerca obiettivo", ma l' output e' meno immediato da interpretare.

Ciao

[Flash30005]

Ottimo il lavoro di Anthony!

Però se si capisse la logica che fa scegliere, con 101 squadre...

5 gironi da 14, 1 da 15 e 1 da 16

Invece di

4 da 14 e 3 da 15.

allora la macro potrebbe determinare sempre il risultato voluto e "ottimizzato"
ma... Esiste questa logica?

Ciao

[gudmund]

Ti dirò, questa macro è più di quanto speravo
io speravo di ottenere 4 cifre secche, ma quello che hai fatto è molto di più.
Ci sono tutte le combinazioni possibili, così mi posso scegliere quella più adatta, anche perché a dirla tutta ci sono un altro paio esigenze che non ho spiegato per non complicare troppo la cosa.
Invece la tua macro va oltre
GRANDE!!
Mo me la devo studiare passo passo col debugger, per capire bene il procedimento
GrazieGrazie

[gudmund]

Ottimo il lavoro di Anthony!

Però se si capisse la logica che fa scegliere, con 101 squadre...

5 gironi da 14, 1 da 15 e 1 da 16

Invece di

4 da 14 e 3 da 15.

allora la macro potrebbe determinare sempre il risultato voluto e "ottimizzato"
ma... Esiste questa logica?

Ciao

Scusa, Flash, Rispondevo ad Anthony mentre tu scrivevi la tua risposta.
La logica fondamentale è avere il più possibile gironi piccoli, quindi da 13 o da 14 ( che sono la stessa cosa, perche in quelli da 13, un squadra a turno riposa, quindi è come se fossero 14) e meno possibile da 15 o da 16
ci sono un altro paio di restrizioni che non ho spiegato, ma mi bastava questo; me le sarei fatte a mano.
Con la macro di Anthony, invece ho tutte le possibili combinazioni, quindi mi basta scegliere quella più adatta.
Ciao

[Anthony47]

Penso che la macro sia semplice da decodificare, la chiave sono quei For /Next annidati e la If al centro.
Se pensi di dover elaborare oltre 1000 squadre allora potrebbe essere utile aggiungere due If dopo il For L e il For M, come qui sotto elencato:

Codice: Seleziona tutto

For L = MaxC To 0 Step -1
If J * BaseN + K * (BaseN + 1) > NumSq Then Exit For
For M = MaxC To 0 Step -1
If J * BaseN + K * (BaseN + 1) + L * (BaseN + 2) > NumSq Then Exit For


Se ti interessa avere "tutte" le combinazioni ovviamente eliminerai la riga If FlaOk = True And etc etc, o cambierai la soglia di confronto.

Ciao