h2. Indicaţii de rezolvare
Problema este o aplicatie a metodei backtracking. Aceasta 'solutie':job_detail/374752?action=view-source garanteaza generarea submultimilor in ordine lexicografica.
Această problemă este o aplicaţie a 'metodei backtracking':http://en.wikipedia.org/wiki/Backtracking. 'Aici':job_detail/374752?action=view-source se găseşte o soluţie ce garantează generarea submulţimilor în ordine lexicografică.
Problema se mai poate rezolva si folosind reprezentarea binara a numerelor. Daca suntem la submultimea $i$ si daca al $j-1$-lea bit din numar este $1$ atunci $j$ va face parte din submultimea $i$. Exemplu: daca $i=5$, $5{~(2)~}=101$ deci elementele $1$ si $3$ fac parte din submultimea a $5$-a. O sursa ce foloseste aceasta idee poate fi gasita 'aici':job_detail/374753?action=view-source.
Aplicaţia se mai poate rezolva şi folosind reprezentarea binară a numerelor. Recomand următorul articol ce tratează în detaliu aceste operaţii: '„Optimizarea programelor folosind operaţii pe biţi”':http://www.google.ro/url?sa=t&source=web&ct=res&cd=3&ved=0CBIQFjAC&url=http%3A%2F%2Fwww.ginfo.ro%2Frevista%2F14_5%2Ffocus.pdf&rct=j&q=opera%C5%A3ii+pe+bi%C5%A3i+cosmin+negru%C5%9Feri&ei=yqcuS7ndB5CUmAOts7yKCQ&usg=AFQjCNEkRFe0NcETCbGQYtwxtZiLl6-lIQ&sig2=u4zPps2-woQOLMdbRDyM4A. Dacă suntem la submulţimea cu indicele $idx$, dacă al $(j-1)$-lea bit din număr este $1$, atunci $j$ va face parte din submulţimea cu indexul $idx$. Iată un exemplu: dacă $idx = 5$ avem următoarea reprezentare în baza $2$ a acestui index: $5{~(2)~} = 101$. În concluzie, elementele $1$ şi $3$ fac parte din submulţimea a $5$-a. O sursă ce foloseşte această idee poate fi găsită 'aici':job_detail/374753?action=view-source.
O alta idee de rezolvare poate fi cea de la problema 'combinari':problema/combinari, generandu-se toate combinarile de $n$ luate cate $k$, unde $k$ ia pe rand valori de la $1$ la $n$. Toate combinarile de $n$ luate cate $k$ sunt de fapt toate submultimile cu k elemente. O sursa ce foloseste aceasta idee poate fi gasita 'aici':job_detail/374897?action=view-source.
O altă idee de rezolvare poate fi cea de la problema 'Combinări':problema/combinari, generându-se toate combinările de $n$ luate câte $k$, unde $k$ ia pe rând valori de la $1$ la $n$. Toate combinările de $n$ luate câte $k$ sunt de fapt toate submulţimile cu $k$ elemente. O sursă ce foloseşte această idee poate fi găsită 'aici':job_detail/374897?action=view-source.
Se observa ca daca sortam submultimile in ordine lexicografica, primele $2^n-1^$ submultimi incep cu cifra $1$, urmatoarele $2^n-2^$ submultimi incep cu cifra $2$, ... , ultima submultime incepe cu cifra $n$. Daca se stie numarul unei submultimi, dupa ce acestea au fost sortate in ordine lexicografica, se pot afla elementele submultimii. O sursa ce foloseste aceasta idee poate fi gasita 'aici':job_detail/374751?action=view-source.
Se observă că dacă sortăm submulţimile în ordine lexicografică, primele $2^n-1^$ submulţimi încep cu cifra $1$, următoarele $2^n-2^$ submulţimi încep cu cifra $2$, ... , ultima submulţime începe cu cifra $n$. Dacă se ştie numărul unei submulţimi, după ce acestea au fost sortate în ordine lexicografică, se pot afla elementele submulţimii. O sursă ce foloseşte această idee poate fi gasită 'aici':job_detail/374751?action=view-source.
Menţionăm în final că, indiferent de ideea de rezolvare folosită, soluţiile au complexitate exponenţială.
h2. Aplicaţii
# 'Jocul Flip':problema/flip
# 'Elimin':problema/elimin
# 'Numere3':problema/numere3
# 'Numere8':problema/numere8
# 'Sortari':problema/sortari
# 'Frac':problema/frac
# 'Ture':problema/ture
# 'Zebughil':problema/zebughil
# 'Sobo':problema/sobo
# 'Gather':problema/gather
# 'Boom':problema/boom
# 'Afacere':problema/afacere
# 'Reteta':problema/reteta
== include(page="template/taskfooter" task_id="submultimi") ==
