Obidream ha scritto:Per curiosità ho provato una versione ricorsiva, di cui non sono neanche troppo sicuro, sul mio hardware modesto siamo ben sotto i 7 secondi d'esecuzione...
Per l'array
v credo sia sufficiente una dimensione pari a $k$, inoltre, affinché siano calcolate le combinazioni semplici di $n$ (e non $n-1$) elementi, bisogna modificare la condizione dei for all'interno della funzione gen_comb() in
<=N.
Apportando le suddette modifiche e qualche piccola semplificazione ho ottenuto il seguente codice:
- Codice:
#include <stdio.h>
#define N 7
#define K 4
void print_comb(const unsigned int *v)
{
for(unsigned int i = 0; i < K; ++i)
{
printf("%2d ", v[i]);
}
printf("\n");
}
void gen_comb(unsigned int *v, const unsigned int p)
{
if(p < K)
{
unsigned int i = 1;
if(p)
{
i += v[p - 1];
}
for( ; i <= N; ++i)
{
v[p] = i;
gen_comb(v, p + 1);
}
}
else
{
print_comb(v);
}
}
int main()
{
unsigned int v[K];
gen_comb(v, 0);
return 0;
}
Per $n=30$ e $k=19$, e rimuovendo l'output, il tempo di esecuzione si aggira sui 18''. Nelle stesse condizioni il programma che ho postato nelle pagine precedenti impiega circa 2''. Ora non so quanto sia rigoroso il test che ho effettuato, ma penso che il punto sia un altro, ossia che una versione ricorsiva sia di più difficile utilizzo rispetto ad una iterativa in grado di passare da una generica combinazione a quella successiva (per esempio nel tuo codice la funzione print_comb() deve essere richiamata per forza dalla funzione gen_comb() e non dal main()).
ZfreS ha scritto:Ok, osservando le combinazioni si nota che ogni elemento raggiunge un valore massimo, ma hai detto che i sono diversi modi di formalizzarlo, la mia domanda è: come ci si arriva? Quella formula è sempre valida?
Come già detto nel precedente post, quella formula è sempre valida nel momento in cui il set di elementi è costituito dagli interi che vanno da $0$ a $n-1$ e le combinazioni sono esplicitate utilizzando l'approccio:
ZfreS ha scritto:sono: {0,1,2} {0,1,3} {0,1,4} {0,2,3} {0,2,4} {0,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4}.
Per quanto riguarda l'altra domanda credo di non aver ben capito quale sia il tuo dubbio!
Provo a metterla diversamente:
- il massimo valore assumibile dall'ultimo elemento della generica combinazione è $n-1$;
- il massimo valore assumibile dal penultimo elemento della generica combinazione è $n-2$;
- il massimo valore assumibile dal terzultimo elemento della generica combinazione è $n-3$;
- ...
Ovviamente tale formulazione è equivalente a quella postata in precedenza $MAX(i)=n-k+i$
Chi dorme in democrazia, si sveglia in dittatura.