Devo dire che trovo il problema molto interessante, quindi mi sono messo a pensarci un po' sopra
La prima cosa che ho cercato di fare è semplificare il problema, ragionando non subito in termini di gruppi di elementi, ma in termini di numerosità dei sottogruppi.
Mi spiego con un esempio : indico con M = [x1, x2, ... , xm] l'array di interi positivi da partizionare e con n il numero di parti ( = sottogruppi) contigue in cui partizionarlo.
Con m indicherò invece il numero di elementi di M.
Poniamo ora m = 7 e n = 4, che è un caso abbastanza ampio da mostrare il funzionamento dell'algoritmo ricorsivo che ho usato. Alcune partizioni di M potrebbero essere le seguenti :
[x1] [x2] [x3] [x4 x5 x6 x7]
[x1] [x2] [x3 x4] [x5 x6 x7]
...
[x1 x2] [x3] [x4] [x5 x6 x7]
[x1 x2] [x3] [x4 x5] [x6 x7]
...
[x1 x2 x3 x4] [x5] [x6] [x7]
Come detto ho preferito ragionare in termini di numerosità dei sottogruppi, quindi le precedenti partizioni le indicherò con :
1 1 1 4
1 1 2 3
...
2 1 1 3
2 1 2 2
...
4 1 1 1
Visto che i gruppi sono contigui, le due scritture sono analoghe: una volta stabilito il numero di elementi delle diverse parti, cioè, si ritrova l'equivalente partizione semplicemente raggruppando gli elementi di M dall'inizio alla fine.
Se si riesce a trovare (e memorizzare) tutte le possibili combinazioni di numerosità dei sottogruppi, quindi, per risolvere il problema basterà in ordine :
- trovare la partizione degli elementi corrispondente alle numerosità dei sottogruppi.
- calcolare in ogni partizione la somma di ogni sottogruppo
- calcolare un indice che descriva la bontà della partizione considerata (ad esempio la differenza tra la maggiore e la minore somma dei sottogruppi di elementi)
- trovare la partizione con l'indice migliore (la minore differenza nel caso sopra considerato).
Avevamo visto che nel caso n = 2 è immediato trovare il numero di combinazioni, che sono esattamente m - 1.
Con l'esempio n = 3 avevamo visto che si poteva fissare il numero di elementi del primo gruppo (che va fatto variare in seguito!), e partizionare il blocco rimanente come nel caso n = 2.
Quindi una funzione ricorsiva potrebbe funzionare in questo modo : se n = 2 restituisce la lista di tutte le possibili combinazioni di numerosità dei sottogruppi {(1, m-1), (2, m-2), ... , (m-1, 1)}
Se n > 2 invece nella funzione si inizierà un ciclo in cui ciclicamente si fissa la numerosità del primo gruppo (che varierà da 1 a m - n + 1) e si richiama ricorsivamente la funzione per dividere gli elementi restanti in n - 1 parti.
La ricorsione continua fino a quando non si arriva a n = 2.
Le combinazioni di ogni chiamata verranno integrate con le parti che si stanno tenendo fisse (ma fatte poi variare fino a considerare tutti i casi).
Posto un grafico che mostra l'andamento della funzione per il caso m = 7 e n = 4.
Il simbolo -> (m, n) indicherà la chiamata ricorsiva alla funzione con m elementi da dividere in n parti. Quando n sara' diverso da 2 si vedranno in colonna tutti i possibili valori, fissati, della numerosità del primo sottogruppo, che saranno poi fatti variare.
Quando si arriva a n = 2 si vedranno incolonnati tutti i possibili modi di inserire gli elementi nei due gruppi. Infine il simbolo <- indicherà il momento in cui, esaurite tutte le combinazioni, la funzione restituirà al livello precedente l'insieme delle combinazioni possibili, per integrarle alle parti che si stanno mantenendo fisse.
Ecco il grafico :
-> (7, 4)
1 ? ? ? -> (6, 3)
1 ? ? -> (5, 2)
1 4
2 3
3 2
1 1 4 <- 4 1
1 2 3
1 3 2
1 4 1
_____
2 ? ? -> (4, 2)
1 3
2 2
2 1 3 <- 3 1
2 2 2
2 3 1
_____
3 ? ? -> (3, 2)
1 2
3 1 2 <- 2 1
3 2 1
_____
4 ? ? -> (2, 2)
4 1 1 <- 1 1
1 1 1 4 <-
1 1 2 3
1 1 3 2
1 1 4 1
1 2 1 3
1 2 2 2
1 2 3 1
1 3 1 2
1 3 2 1
1 4 1 1
_______
2 ? ? ? -> (5, 3)
1 ? ? -> (4, 2)
1 3
2 2
1 1 3 <- 3 1
1 2 2
1 3 1
_____
2 ? ? -> (3, 2)
1 2
2 1 2 <- 2 1
2 2 1
_____
3 ? ? -> (2, 2)
3 1 1 <- 1 1
2 1 1 3 <-
2 1 2 2
2 1 3 1
2 2 1 2
2 2 2 1
2 3 1 1
_______
3 ? ? ? -> (4, 3)
1 ? ? -> (3, 2)
1 2
1 1 2 <- 2 1
1 2 1
_____
2 ? ? -> (2, 2)
2 1 1 <- 1 1
3 1 1 2 <-
3 1 2 1
3 2 1 1
_______
4 ? ? ? -> (3, 3)
_____
1 ? ? -> (2, 2)
1 1 1 <- 1 1
4 1 1 1 <-
Nel caso in esame quindi, tutte le combinazioni in cui si può partizionare il vettore inserito (in termini di numerosità dei sottogruppi) sono :
1 1 1 4
1 1 2 3
1 1 3 2
1 1 4 1
1 2 1 3
1 2 2 2
1 2 3 1
1 3 1 2
1 3 2 1
1 4 1 1
2 1 1 3
2 1 2 2
2 1 3 1
2 2 1 2
2 2 2 1
2 3 1 1
3 1 1 2
3 1 2 1
3 2 1 1
4 1 1 1
Scusate la lunghezza del post, volevo spiegare chiaramente il procedimento che ho seguito. Come detto arrivati a questo punto il resto viene da sè.
Ditemi pure se pensate che esista una soluzione migliore.
Sicuramente il tutto potrebbe essere fatto in maniera più efficiente ed elegante, senza salvarsi prima le numerosità dei gruppi per ricavare in un secondo momento le partizioni corrispondenti.
Penso però che in questo modo il procedimento risulti più intuitivo e facile da leggere/testare.
Per ora non scrivo il codice della funzione, anche perché vorrei ricevere prima qualche feedback dal resto degli utenti, sempre che quanto ho scritto non sia troppo noioso/delirante da leggere
@cobra.91 : Se pensi che questo possa essere un punto di partenza sono contento, ma vorrei che provassi a scrivere tu la soluzione di questo algoritmo (o un altro che verrà proposto).
Dovresti anche chiarire quanto ci chiedevamo in precedenza, ovvero quale criterio usare per stabilire la migliore partizione nel caso n > 2.
Ps: Non riesco a rendere a replicare l'indentazione del grafico che avevo in notepad ++, spero si capisca comunque