ALGORITMO IN JAVA

di il
6 risposte

ALGORITMO IN JAVA

Ciao a tutti, spero di non aver sbagliato sezione .
Vi descrivo subito il mio problema. Dovrei creare un algoritmo che , dato un array M di numeri interi positivi ed n un intero positivo, esso partizioni M in n parti contigue in modo che non ci sia un partizione la cui somma sia molto più grande della somma di un'altra partizione.ESEMPIO:

dati
n = 2;
M = 3 2 8 4 7;

l'algoritmo dovrebbe partizionare M nel seguente modo,
(3 2 8 ) prima partizione, somma = 13;
(4 7) seconda partizione, somma = 11;

,dal momento che la somma delle due partizioni è quella che si avvicina di più, rispetto a tutte le altre possibili partizioni, ad essere uguale.

Ragazzi non vi chiedo l'esercizio svolto ma semplicemente un aiuto ad impostarlo, purtroppo lavoro ed ho poco tempo da dedicargli.
Se mi aiutaste ve ne sarei grato. Intanto grazie in anticipo.

6 Risposte

  • Re: ALGORITMO IN JAVA

    cobra.91 ha scritto:


    dato un array M di numeri interi positivi ed n un intero positivo, esso partizioni M in n parti contigue in modo che non ci sia un partizione la cui somma sia molto più grande della somma di un'altra partizione.
    A grandi linee ... devi "provare" tutti i possibili casi di partizionamento.
    Riprendiamo il tuo esempio con i dati 3 2 8 4 7. Con n=2 è abbastanza semplice:

    Provi:
    [3] [2 8 4 7] (somme: 3 e 21)

    poi provi:
    [3 2] [8 4 7] (somme: 5 e 19)

    poi provi:
    [3 2 8] [4 7] (somme: 13 e 11)

    poi provi:
    [3 2 8 4] [7] (somme: 17 e 7)

    Il partizionamento con le somme più vicine è chiaramente il terzo (proprio quello che hai detto tu). Man mano che provi i partizionamenti, dovresti tenerti le informazioni sul partizionamento "migliore" in quel momento.

    Con n=2 ripeto che è facile ... con n maggiore di 2, è sicuramente meno banale.
  • Re: ALGORITMO IN JAVA

    Ciao, innanzi tutto grazie per la risposta. Ho pensato anche io a trovare tutti i possibili casi di partizionamento, il problema per me è che se avessi un ordine del tipo, tutti i possibili sottoinsiemi di ordine k saprei come fare ma in questo caso, visto che il sottoinsieme può contenere da 1 a n numeri non mi viene in mente come procedere:(
  • Re: ALGORITMO IN JAVA

    cobra.91 ha scritto:


    Ciao, innanzi tutto grazie per la risposta. Ho pensato anche io a trovare tutti i possibili casi di partizionamento, il problema per me è che se avessi un ordine del tipo, tutti i possibili sottoinsiemi di ordine k saprei come fare ma in questo caso, visto che il sottoinsieme può contenere da 1 a n numeri non mi viene in mente come procedere:(
    Credo che lo puoi sicuramente trattare come partizionamento "ricorsivo" (intendo non necessariamente come ricorsione sui metodi).

    Prendiamo es. 4 7 2 6 3 1 5 3 e un n=3
    Parti con [4] [7 2 6 3 1 5 3] e il secondo blocco lo partizioni a sua volta con la stessa logica [7] [2 6 3 1 5 3] ... [7 2] [6 3 1 5 3] ecc.....
    Poi farai [4 7] [2 6 3 1 5 3] e il secondo blocco di nuovo [2] [6 3 1 5 3] ... [2 6] [3 1 5 3] ecc...

    C'è sicuramente il modo di "generalizzarlo". Ma non ho purtroppo tempo ora di fare ulteriori ragionamenti.
  • Re: ALGORITMO IN JAVA

    Beh se avessi n = 3 potresti ad esempio fissare il numero di elementi del primo gruppo (chiamiamolo n1), e poi fai quanto è descritto sopra per il resto del vettore.

    Ad esempio fissi n1 = 2 (sempre con M tratto del tuo esempio). Quindi G1 = [3 2] . Rimane da dividere l' insieme [8 4 7]. Seguendo il procedimento sopra poi questo gruppo lo puoi dividere in [8] [4 7] o in [8 4] [7].

    Ovviamente poi devi far variare n1 in tutto il range possibile di valori, in questo caso un gruppo può contenere al massimo 3 elementi, altrimenti avresti un gruppo vuoto.

    n1 = 1

    [3] [2] [8 4 7] (somme : 3 2 19)
    [3] [2 8] [4 7] (somme : 3 10 11)
    [3] [2 8 4] [7] (somme : 3 14 7)

    n1 = 2

    [3 2] [8] [4 7] (somme : 5 8 11)
    [3 2] [8 4] [7] (somme : 5 12 7)

    n1 = 3

    [3 2 8] [4] [7] (somme : 13 4 7)

    Devi però anche scegliere il criterio con cui stabilisci la migliore partizione. Potresti volere che sia minima la differenza tra la maggiore somma e la minore somma (in questo caso nel caso con somme: 5 8 11). Ma potresti anche volere la partizione in cui le somme siano "più vicine" tra di loro (ad esempio la partizione con minor varianza).

    Inoltre il problema è riuscire a scrivere, ma soprattutto generalizzare l'algoritmo.
    Per scriverlo potresti seguire questa idea: crei un primo ciclo for in cui fissi la prima soglia (il primo punto in cui "tagli" il vettore). Poi in un ciclo innestato fai variare la seconda soglia in tutti i casi possibili.
    Per ogni combinazione devi poi calcolarti l' indice di interesse, e salvarti la combinazione migliore.

    Ma se avessi n = 10 dovresti scrivere 9 cicli uno dentro all'altro con questa soluzione, serve qualcosa di più furbo ...

    Ps: Ho visto dopo l'ultimo messaggio inserito, posto comunque
  • Re: ALGORITMO IN JAVA

    Ansharja ha scritto:


    Devi però anche scegliere il criterio con cui stabilisci la migliore partizione. Potresti volere che sia minima la differenza tra la maggiore somma e la minore somma (in questo caso nel caso con somme: 5 8 11). Ma potresti anche volere la partizione in cui le somme siano "più vicine" tra di loro (ad esempio la partizione con minor varianza).
    Esattamente, grazie Ansharja. Anche a me prima era venuta l'intuizione che con n > 2 c'è qualcosa "in più" da valutare. Con n=2 è banale, l'ho detto prima, ci sono solo 2 somme. Con 3+ somme c'è da valutare la logica per determinare quale situazione "è meglio".
  • Re: ALGORITMO IN JAVA

    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
Devi accedere o registrarti per scrivere nel forum
6 risposte