Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Re: Problema di combinatoria

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..

Re: Problema di combinatoria

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.

Re: Problema di combinatoria

10/07/2019, 13:42

Ma per generare tutte le combinazioni, utilizzo la formula classica o c'è qualche altro modo?

Re: Problema di combinatoria

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?

Re: Problema di combinatoria

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.

Re: Problema di combinatoria

10/07/2019, 14:13

Più per curiosità che per altro, quanto ci impiega la versione ricorsiva? Stai usando Python?

Re: Problema di combinatoria

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.

Re: Problema di combinatoria

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.

Re: Problema di combinatoria

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!

Re: Problema di combinatoria

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?
Rispondi al messaggio


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.