[C] Algoritmo per possibili sottoinsiemi di cardinalita k. (GRAFI)
Semplifico il problema (molto famoso nella matematica e nella combinatoria):
ho un vettore di interi da 0 a N e voglio trovare tutti i possibili sottoinsiemi di k elementi, per poter poi analizzare ogni sottoinsieme e vedere se rispettano certe caratteristiche,
per i più interessati:
In particolare sto lavorando su un grafo e voglio trovare le possibili cricche di ordine k, e per farlo voglio analizzare tutti i sottografi di ordine k per vedere quali sono connessi e quali no.
Grazie!
ho un vettore di interi da 0 a N e voglio trovare tutti i possibili sottoinsiemi di k elementi, per poter poi analizzare ogni sottoinsieme e vedere se rispettano certe caratteristiche,
per i più interessati:
In particolare sto lavorando su un grafo e voglio trovare le possibili cricche di ordine k, e per farlo voglio analizzare tutti i sottografi di ordine k per vedere quali sono connessi e quali no.
Grazie!
Risposte
In genere penso si cerchi di evitare di farlo, anche perché la complessità è tutt'altro che trascurabile. Per eliminare le ricorsioni ti basta comunque prendere gli elementi in ordine.
Per esempio per N = 4 e K = 2 si ha:
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4
Nota che il primo elemento va da 1 a N-K+1. I restanti li trovi applicando lo stesso algoritmo al sottoinsieme degli elementi maggiori del primo.
Per esempio per N = 4 e K = 2 si ha:
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4
Nota che il primo elemento va da 1 a N-K+1. I restanti li trovi applicando lo stesso algoritmo al sottoinsieme degli elementi maggiori del primo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo