PDA

Visualizza la versione completa : [C] Algoritmo combinatorio


vAiO
10-01-2005, 14:25
Salve ragazzi, vediamo se qualcuno puà aiutarmi. Sto cercando di implementare in C un algoritmo che mi faccia la seguente cosa:

ho un insieme di N elementi, devo poter tovare un modo per verificare tutte le possibili combinazioni di N con k elementi. Cioè se ho un insieme di 4 elementi, devo poter riuscire a fare:

1 1 1 1 2 2 2 1 1 1 2 2 etc
2 2 3 2 3 3 4 2 3 4 3 4
3 3 4 4 4 1 1
4


insomma poter passare tutte le combinazioni possibili. Ora risco a farlo quando devo passare N-1 elementi, ma nn trovo il modo (ricorsivo o meno) di farlo per tutto l'insieme, Se qualcuno ha un'idea oppure documentazione dove posso guardare mi farebbe un favore, Grazie!

Trusty
10-01-2005, 15:17
Posta il codice e vediamo..... :ciauz:

anx721
10-01-2005, 16:12
io non ho capito cosa vuoi fare

vAiO
10-01-2005, 17:46
ok scendo nei dettagli:

ho una linked list con tot elementi (ogni elemento contiene una coppia di numeri)

In parole povere se nella lista ho n elementi, devo trovare il modo per poter esaminare ogni sottoinsieme di elementi della lista partendo dal + grande al + piccolo. Esempio, se ho 4 elementi, prima esamino il primo, il secondo, il terzo. Poi il primo il terzo e il quarto. Creando quindi tutte le combinazioni possibili. Poi se una certa condizione non viene verificata passo ad esaminare sottoinsiemi di n-1 elementi poi n-2 e così via. QUindi per esempio passo a 2 elementi e quindi tutte le combinazioni tipo 12-13-14-23-21-24 etc.
Il codice che ho fatto io è abb spartano solo che non riesco ad esaminare sottoinsiemi che abbiano cardinalità superiori a n-2



int test_cheked_gruppo(int partialMarito, int partialMoglie) { //calcola la somma delle età dei mariti e delle mogli solo degli elementi con chk=1
struct community *cursor;
cursor=head;
int sommaMarito=partialMarito;
int sommaMoglie=partialMoglie;
while (cursor!=NULL) {
if (cursor->chk==1) {
sommaMarito = sommaMarito + cursor->etaMarito;
sommaMoglie = sommaMoglie + cursor->etaMoglie;
}
cursor=cursor->next;
}
if (sommaMarito == sommaMoglie) return 1;
else return 0;
}

int max_gruppo_1(int partialMarito, int partialMoglie) { //verifica la condizione di somma età marito/moglie con cardinalità 1);
struct community *cursor,*verify;
cursor=head;
verify=head;
while (verify!=NULL) { //inizia a diminuire la cardinalità massima di un elemento per volta
verify->chk=0;
if (test_cheked_gruppo(partialMarito,partialMoglie) == 1) return 1;
else {
reset_comunita(0);
verify=verify->next;
}
}
return 0;
}

int max_gruppo_full() { //verifica la condizione di somma età marito/moglie
struct community *cursor,*verify,*set_use;
cursor=head;
verify=head;
set_use=head;
if (test_cheked_gruppo(0,0) == 1) return 1; //effettua il calcolo della somma delle età dei mariti/mogli in tutti gli elementi della comunità
cursor=head;
if (max_gruppo_1(0,0) == 1) return 1;
set_use->chk=2;
while (set_use!=NULL) {
if (max_gruppo_1(set_use->etaMarito,set_use->etaMoglie) == 1) return 1;
else {
reset_comunita(2);
reset_comunita(0);
set_use=set_use->next;
}
}
return 0;
}

Loading