Discussioni su argomenti di Informatica
09/07/2019, 20:44
Solo come piccola osservazione.. Il numero di sottoinsiemi di un insieme dato è \(2^n\). Per \(n = 50\) hai quindi \(2^{50} = 1125899906842624 \approx 10^{15}\) (se ho contato bene le cifre..). Anche supponendo di metterci un nanosecondo a trovarne uno, ci metteresti \(10^6\) secondi (quasi 12 giorni). E questo solo per iterare su ognuno di essi. Se li devi memorizzare, supponendo di usare solo 50 bit, sono qualcosa tipo 5000 TB credo..
10/07/2019, 09:17
Si SuperSquirrel, l'output aspettato è proprio quello. Provo arealizzare ciò che dici.
In effetti 50 sono troppi, diciamo allora 20-30.
10/07/2019, 13:42
Ma per generare tutte le combinazioni, utilizzo la formula classica o c'è qualche altro modo?
10/07/2019, 13:48
Il metodo più semplice è ovviamente quello di usare una funzione ricorsiva. Qual'è la formula classica a cui stai facendo riferimento?
10/07/2019, 14:01
Ho provato con 30 elementi e impiega circa 29'', ovviamente rimuovendo l'output.
La mia implementazione non è ricorsiva e si basa sulla modifica di un array di $k$ elementi contenente gli indici della generica combinazione semplice. I suddetti indici si riferiscono ad un secondo array che contiene gli $n$ elementi che costituiscono l'insieme di partenza.
10/07/2019, 14:13
Più per curiosità che per altro, quanto ci impiega la versione ricorsiva? Stai usando Python?
10/07/2019, 15:00
La formula classica a cui mi riferisco è il coefficiente binomiale $(n!)/(k!(n-k)!)$. Questa è la formula delle combinazioni semplici, penso quella che ha implementato Super Squirrel.
Ultima modifica di
ZfreS il 10/07/2019, 16:20, modificato 1 volta in totale.
10/07/2019, 15:02
Ma vuoi ottenere solo il numero di questi sottoinsiemi o la loro lista? Perché se è solo il numero l'esercizio è molto più semplice.
10/07/2019, 15:55
apatriarca ha scritto:Più per curiosità che per altro, quanto ci impiega la versione ricorsiva? Stai usando Python?
Non saprei, in quanto la funzione che genera la combinazione successiva è iterativa. Utilizzo C/C++.
In pratica l'implementazione può essere schematizzata nel seguente modo:
- Codice:
bool next_combination(unsigned int n, unsigned int k, unsigned int u[k])
{
...
}
int main()
{
const unsigned int n = 5;
const unsigned int k = 3; //per esempio
char v[n] = {a, b, c, d, e};
unsigned int u[k] = {0, 1, 2}
do
{
for(unsigned int i = 0; i < k; ++i)
{
cout << v[u[i]] << " ";
}
cout << endl;
}
while(next_combination(n, k, u));
}
La formula classica a cui mi riferisco è il coefficiente binomiale n!k!(n−k)!. Questa è la formula delle combinazioni semplici, penso quella che ha implementato Super Squirrel.
Come detto da apatriarca, quella formula è utile per trovare il numero di combinazioni, non per ottenerne la lista!
10/07/2019, 16:20
No, la lista mi serve, ma pensavo che comunque per ottenere le combinazioni servisse la formula. Ma la funzione bool rimane vuota?
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.