[C] Algoritmo combinatorio

[vAiO]

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]

Posta il codice e vediamo.....

[anx721]

io non ho capito cosa vuoi fare

[vAiO]

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;
}