Generare submultimi in alta ordine

[•cipri_tom]

Salut,

Ma lupt cu urmatoarea problema de cateva zile si nu prea imi iese cum vreau . Ma gandeam ca poate aveti voi putina inspiratie sau imi vindeti un pont. Merci.

Dandu-se un sir a, de lungime m, sa se genereze toate sirurile b cu proprietatea 0 <= b[j] <= a[j], j = 1, m, in ordinea crescatoare a sumei elementelor.
Exemplu:

a = {2, 2, 2}	b0 = { 0, 0, 0 }
	b1 = { 1, 0, 0 }
	b3 = { 0, 1, 0 }
	b6 = { 0, 0, 1 }
	b2 = { 2, 0, 0 }
	b4 = { 1, 1, 0 }
	b5 = { 0, 2, 0 }
	b7 = { 1, 0, 1 }
	b8 = { 0, 1, 1 }
	b9 = { 0, 0, 2 }

Am reusit si sa le fac in alta ordine cu un backtracking. Apoi le-am reordonat cautand liniar sirurile de fiecare ordine, dar desigur asta nu e destul de eficient.

Am o idee care se bazeaza pe generarea consecutiva. Initial le construim pe cele de suma 1, care e doar o matrice cu 1 pe diagonala principala.
Apoi, fiecare suma S se obtine prin insumarea element cu element a unui sir de suma 1 si un sir de suma S-1. Problema e cum sa nu generam sirurile de 2 ori. Am reusit cand sirul a are aceleasi elemente ({2, 2, 2}), dar nu reusesc cand elementele sunt diferite ({2, 3, 2}).

Idei?
Pot posta ce cod am pana acum, desi nu e foarte elegant.

P.S. Nu sunt sigur daca ar trebui categorizat ca tema. Nu e pt scoala, e pt lucru  .

[•tudorv96]

Care este ordinea de generare cand suma este aceeasi? (b-urile alea sunt sortate sau nu?)

[•cipri_tom]

deocamdata nu este o ordine specifica atunci cand suma este aceeasi, deci orice varianta e buna. Cu cat mai eficienta, cu atat mai bine .
Ordinea pe care am pus-o eu la b-uri rezulta din ideea precizata, obtinem un sir de suma S dintr-un sir de suma S-1 si un sir de suma 1. In acest fel generez mereu doar siruri valide.

[•tudorv96]

Daca nu ma insel, tot timpul vor exista (a[1] + 1) * (a[2] + 1) * (a[3] + 1) *... * (a[m] + 1) solutii. (Incerci sa obtii toate combinatiile posibile). Nu exista algoritmi care au complexitatea mai buna decat Backtracking.

LE: Se pot aplica optimizari, precum cele care le-ai precizat mai sus, dar in fond tot backtracking este 

Mai sunt si alte restrictii si precizari?

[•cipri_tom]

Daca nu ma insel, tot timpul vor exista (a[1] + 1) * (a[2] + 1) * (a[3] + 1) *... * (a[m] + 1) solutii. (Incerci sa obtii toate combinatiile posibile). Nu exista algoritmi care au complexitatea mai buna decat Backtracking.

Da, asa este, avem nevoie de toate acele solutii, insa in generarea lor trebuie sa incercam cat mai putine care sunt invalide  .

LE: Se pot aplica optimizari, precum cele care le-ai precizat mai sus, dar in fond tot backtracking este 

Prin backtracking inteleg acele metode in care incerci solutii si apoi le verifici. Ideea precizata genereaza direct solutiile bune, fara alte verificari, deci imi suna mai mult a programare dinamica. In fine, e doar terminologie. In final, da, avem nevoie de toate solutiile .

Mai sunt si alte restrictii si precizari?

Nu. Problema nu e din ceva concurs, e din viata reala, deci putem fi flexibili. In final, va trebui sa compar diverse metode pentru a obtine rezultatul si vedem care e mai convenabila in ceea ce priveste timpul de executie si memoria folosita. Daca se poate si paraleliza, ar fi perfect, dar aia nu e o prioritate si ma indoiesc ca se poate .

[•tudorv96]

Prin backtracking inteleg acele metode in care incerci solutii si apoi le verifici.

Da, iei pe rand fiecare combinatie posibila de numere. Insa, pentru a afisa in ordine crescatoare dupa S si pentru a evita solutiile invalide apar niste complicatii. 

O metoda ar fi sa faci pentru toate S-urile un back(int k, int sum, int sum_now) (k ii pozitia curenta pentru care generezi, sum ii suma la care vrei sa se ajunga, sum_now ii suma curenta a numerelor pana la pozitia k-1, inclusiv)
De asemenea, retinerii sumei partiale pentru fiecare element ajuta pentru calcularea mai rapida. (sp[ i ] = sp[ i-1 ] + a[ i ])

pentru fiecare pozitie k va fi un for in care se testeaza elementele:

Cod:

void back(int k, int sum, int sum_now) {
        for(int i = max (0, sum - sum_now - (sp[ m ] - sp[ k ]); i <= min(sum - sum_now, a[ k ]); ++i) {
               v[ k ] = i;
               back(k+1, sum, sum_now + i);
       }
}

max (0, sum - sum_now - (sp[ m ] - sp[ k ]) - verifica cazul in care toate elementele de la k+1 pana la m vor fi maxime, astfel incat sa se evite problema solutiilor invalide (in care suma obinuta in back e mai mica decat ar trebui sa fie)

Nu ar trebui sa se obtina nici duplicate, nici solutii invalide cand ajungi la k maxim. 

Nu. Problema nu e din ceva concurs, e din viata reala, deci putem fi flexibili.

Orice alta precizare poate modifica radical algoritmul, inclusiv ordinea aceea cand S-urile sunt egale.