Kombinacije bez ponavljanjaImam jedno pitanje. Radim sa kombinacijama bez ponavljanja
kod kojih nije bitan raspored elemenata, vec su permutacije
{2 5 6 9} i {2 9 6 5} iste i nema potrebe da ih ponovo uzimamo
u obzir nego cemo napisati onu kod koje su cifre sortirane.
Prilazem i mali kod koji sluzi samo za primjer ovih permutacija.
Code:
#include <stdio.h>
#define BROJKOMB 4
#define ODBROJ 8
char komb[BROJKOMB];
void print_c(char *array, int size){
int i;
for(i=0;i<size;i++)
printf("%d ",array[i]);
printf("\n");
}
void gen_c(char *array, int c, int broj, int od){
if(c == broj)
print_c(array,broj);
else
for(array[c] = c?array[c-1]+1:1; array[c] <= od;array[c]++)
gen_c(array,c+1,broj,od);
}
int main(){
gen_c(komb,0,BROJKOMB,ODBROJ);
}
#include <stdio.h>
#define BROJKOMB 4
#define ODBROJ 8
char komb[BROJKOMB];
void print_c(char *array, int size){
int i;
for(i=0;i<size;i++)
printf("%d ",array[i]);
printf("\n");
}
void gen_c(char *array, int c, int broj, int od){
if(c == broj)
print_c(array,broj);
else
for(array[c] = c?array[c-1]+1:1; array[c] <= od;array[c]++)
gen_c(array,c+1,broj,od);
}
int main(){
gen_c(komb,0,BROJKOMB,ODBROJ);
}
Ovaj primjer generise 4 od 8 kombinacije.
Interesuje me da li je moguce na gornjem primjeru izabrati neke
kombinacije od po 4 broja tako da:
ako nekih 6 od 8 brojeva slucajno odabranih bude "ukljuceno",
a ostala dva budu "iskljucena" onda da budemo sigurni da ce
biti odabrana jedna kombinacija od po 4 broja koja u kojoj ce
svi brojevi imati stanje "ukljuceno".
Potrebno je kombinacije 4 od 8 optimalizirati da ih bude sto manje.
Ocigledno je da treba generisati sve 4 od 8 kombinacije i 6 od 8
a zatim gledati koje 4 od 8 kombinacije se najbolje uklapaju, odnosno
najbolje pokrivaju sve 6 od 8 kombinacije.
Ovi brojevi su koristeni samo za primjer, dok rjesenje zahtjeva opcenit slucaj.
Ako se neko nece nasmijati, meni ovaj problem lici na problem ruksaka.
Optimalno dodati kombinaciju, a zatim rijesiti podproblem.
Nisam uspio da dokucim optimalnu strukturu ovog problema tj. nisam uspio
da ga rastavim na podprobleme. Jako je tesko zapisati neko stanje
u kome bi se sistem nalazio nakon sto bismo dodati neku kombinaciju.
Ako neko ima ideju volio bih je cuti.
Unaprijed hvala,
Adnan Bosovic
