Re: Problema di combinatoria

Messaggioda apatriarca » 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..
apatriarca
Moderatore
Moderatore
 
Messaggio: 5264 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Problema di combinatoria

Messaggioda ZfreS » 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.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1767 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda ZfreS » 10/07/2019, 13:42

Ma per generare tutte le combinazioni, utilizzo la formula classica o c'è qualche altro modo?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1768 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda apatriarca » 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?
apatriarca
Moderatore
Moderatore
 
Messaggio: 5265 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Problema di combinatoria

Messaggioda Super Squirrel » 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.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 356 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda apatriarca » 10/07/2019, 14:13

Più per curiosità che per altro, quanto ci impiega la versione ricorsiva? Stai usando Python?
apatriarca
Moderatore
Moderatore
 
Messaggio: 5266 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Problema di combinatoria

Messaggioda ZfreS » 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.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1769 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda apatriarca » 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.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5267 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Problema di combinatoria

Messaggioda Super Squirrel » 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!
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 357 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda ZfreS » 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?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1770 di 4589
Iscritto il: 22/10/2016, 17:52

PrecedenteProssimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite