algoritmo per generare combinazioni di numeri senza ripetizione

Ho controllato quasi tutti i post simili qui ma non sono riuscito a capire come posso fare quello che voglio. Quello che sto cercando è di dare un input in un programma C, diciamo numero 4, e il programma restituisce i seguenti numeri in un array:

1 2 3 4 12 13 14 23 24 34 123 134 124 1234 

Per essere più chiari: se il numero di ingresso è 4, voglio utilizzare le cifre 1-4 e generare tutte le combinazioni possibili di cifre (da combinazioni a 1 cifra a combinazioni a 4 cifre) senza ripetizioni di cifre.

Ho provato il seguente codice:

 #include  /* Prints out a combination like {1, 2} */ void printc(int comb[], int k) { printf("{"); int i; for (i = 0; i = 0) && (comb[i] >= n - k + 1 + i)) { --i; ++comb[i]; } if (comb[0] > n - k) /* Combination (nk, n-k+1, ..., n) reached */ return 0; /* No more combinations can be generated */ /* comb now looks like (..., x, n, n, n, ..., n). Turn it into (..., x, x + 1, x + 2, ...) */ for (i = i + 1; i < k; ++i) comb[i] = comb[i - 1] + 1; return 1; } int main(int argc, char *argv[]) { int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */ int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */ int comb[16]; /* comb[i] is the index of the i-th element in the combination */ /* Setup comb for the initial combination */ int i; for (i = 0; i < k; ++i) comb[i] = i; /* Print the first combination */ printc(comb, k); /* Generate and print all the other combinations */ while (next_comb(comb, k, n)) printc(comb, k); return 0; } 

Il programma sopra mostra il risultato. Voglio ottenere il risultato in qualche modo .. ma non posso perché il codice precedente stampa il risultato in un modo strano.

Usiamo un int per rappresentare un set. Per l’i-esimo bit, se è 1, allora io sono nell’insieme e viceversa.

Prendi un esempio: 1010 (2) = {4,2} 1111 (2) = {4,3,2,1}

Per ogni elemento che sarà considerato, ci sono due scelte: in o non nel set.

Quindi, ci sono 2 ^ n diversi set in totale. E nel mio codice, ho appena elencato ogni ansible int che corrisponde a un set e emette il set corrispondente.

Quindi otteniamo questo codice:

 for(int i=1;i<(1< 

quando n = 4, uscita:

 1 2 12 3 13 23 123 4 14 24 124 34 134 234 1234 

Se vuoi dare la risposta come ordine di dare, basta metterli in una stringa e mettere queste stringhe in vettoriale e ordinarle.

Se n è grande, puoi usare bitset. Ma quando n> 30, potrebbe non essere terminato in ore. Quindi int è efficiente.

Ecco un programma che genera combinazioni di numeri. È scritto in C. Ma potrebbe essere riscritto in qualsiasi altra lingua. Per ora, compila e prova!

 #include  #include  int v[100], stack[100]; int sp,i,n,g; int main() { printf("Dimension of V:"); scanf( "%d",&n); //Input numbers for (i=0 ; i=0) sp=sp-1; // if Bottom of stack is reached then stop if (sp<0) break; // set top of stack from one to zero stack[sp]=0; } return 0; } 

correre per n = 4:

 [[email protected] fin]$ ./comb Dimension of V:4 V[0]=10 V[1]=20 V[2]=30 V[3]=40 running... v[0]=10 v[0]=10 v[1]=20 v[0]=10 v[1]=20 v[2]=30 v[0]=10 v[1]=20 v[2]=30 v[3]=40 v[0]=10 v[1]=20 v[3]=40 v[0]=10 v[2]=30 v[0]=10 v[2]=30 v[3]=40 v[0]=10 v[3]=40 v[1]=20 v[1]=20 v[2]=30 v[1]=20 v[2]=30 v[3]=40 v[1]=20 v[3]=40 v[2]=30 v[2]=30 v[3]=40 v[3]=40