Pagina 2 di 4

Re: Problema di combinatoria

MessaggioInviato: 09/07/2019, 21:44
da apatriarca
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

MessaggioInviato: 10/07/2019, 10:17
da ZfreS
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

MessaggioInviato: 10/07/2019, 14:42
da ZfreS
Ma per generare tutte le combinazioni, utilizzo la formula classica o c'è qualche altro modo?

Re: Problema di combinatoria

MessaggioInviato: 10/07/2019, 14:48
da apatriarca
Il metodo più semplice è ovviamente quello di usare una funzione ricorsiva. Qual'è la formula classica a cui stai facendo riferimento?

Re: Problema di combinatoria

MessaggioInviato: 10/07/2019, 15:01
da Super Squirrel
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

MessaggioInviato: 10/07/2019, 15:13
da apatriarca
Più per curiosità che per altro, quanto ci impiega la versione ricorsiva? Stai usando Python?

Re: Problema di combinatoria

MessaggioInviato: 10/07/2019, 16:00
da ZfreS
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.

Re: Problema di combinatoria

MessaggioInviato: 10/07/2019, 16:02
da apatriarca
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

MessaggioInviato: 10/07/2019, 16:55
da Super Squirrel
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

MessaggioInviato: 10/07/2019, 17:20
da ZfreS
No, la lista mi serve, ma pensavo che comunque per ottenere le combinazioni servisse la formula. Ma la funzione bool rimane vuota?