Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Ottimizzazione codice partizionamento intero
Forum - C/C++ - Ottimizzazione codice partizionamento intero

Avatar
Donto (Normal User)
Newbie


Messaggi: 2
Iscritto: 10/02/2017

Segnala al moderatore
Postato alle 22:01
Venerdì, 10/02/2017
Salve a tutti.

Qualche tempo fa un mio prof ci ha dato, come esercizio da fare a casa, la realizzazione di una funzione di partizione di un numero date k cifre, che fosse, in aggiunta, abbastanza efficiente da non fare affaticare la memoria nel calcolo delle varie sequenze; le partizioni di un numero, come ben saprete, sono tutte le combinazioni possibili di k cifre tali che la loro somma è uguale al numero stesso, ad esempio:

n=6
k=3

Combinazioni possibili:
{4,1,1}
{1,4,1}
{1,1,4}
{3,2,1}
{3,1,2}
{2,1,3}
{2,3,1}
{1,2,3}
{1,3,2}
{2,2,2}

Ovviamente ho già elaborato una soluzione algoritmica in C++, che è la seguente:
Codice sorgente - presumibilmente C++
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int somma(vector<unsigned> p)
  7. {
  8.         int s=0;
  9.        
  10.         for (int i=1; i<p.size(); i++)
  11.         {
  12.                 s+=p[i];
  13.         }
  14.        
  15.         return s;
  16. }
  17.  
  18. void genera_permutazioni(unsigned n,unsigned amici)
  19. {
  20.         vector<unsigned> p(amici,1);
  21.         p[0]=(n-amici+1);
  22.        
  23.         int tmp=0;
  24.        
  25.         while (true)// PEZZO DI CODICE ERRATO PER SEGMENTATION FAULT---> SI OCCUPA DI PARTIZIONARE UN INTERO
  26.         {      
  27.                 do
  28.                 {
  29.                         for (int i=0; i<amici; i++)
  30.                         {
  31.                                 cout<<p[i]<<" ";
  32.                         }
  33.                         cout<<endl;
  34.                 }while(prev_permutation(p.begin(),p.end()));
  35.                
  36.                 for (int i=1; i<amici; i++)
  37.                 {
  38.                         if (p[i]<p[0]-1)
  39.                         {
  40.                                 tmp=i;
  41.                                 break;
  42.                         }
  43.                 }
  44.                        
  45.                 if (tmp==0)
  46.                 {
  47.                         return;
  48.                 }
  49.                        
  50.                 for (int i=1; i<=tmp; i++)
  51.                 {
  52.                         p[i]=p[tmp]+1;
  53.                 }
  54.                        
  55.                 p[0]=(n-somma(p));
  56.                        
  57.                 tmp=0;
  58.         }
  59. }
  60.  
  61. int main()
  62. {
  63.         unsigned n,amici;
  64.  
  65.         cin>>n>>amici;
  66.                
  67.         genera_permutazioni(n,amici);
  68.        
  69.         return 0;
  70. }


In cui, passando i parametri "n" ed "amici" alla funzione "genera_permutazioni", per ogni partizione di base effettuo la permutazione, generando tutte le possibili combinazioni.
Ovviamente il problema è dietro l'angolo: per numeri troppo grandi (orientativamente da 15 in su), il programma ci mette fin troppo ad eseguire le istruzioni, portandomi ad un segmentation_fault per la troppa memoria usata.

Avevo già cercato una soluzione in merito, provando l'approccio con la programmazione dinamica (non andato a buon fine) e col backtracking (valido ma sempre dispendioso in termini di memoria); alla luce delle considerazioni fatte, sapreste indicarmi una soluzione riguardante l'ottimizzazione del calcolo delle partizioni di numeri abbastanza grandi? Ci sto faticando da quasi un mese ma sembro non approdare da nessuna parte :(

PM Quote
Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 14:45
Sabato, 11/02/2017
ciao, al momento sono impegnato per scrivere un pò di codice e conosco poco il c++,
comunque io partirei da un ragionamento semplice (ma non so se porta a miglioramenti o meno...).
dato il tuo esempio


n=6
k=3

Combinazioni possibili:
{4,1,1}
{1,4,1}
{1,1,4}
{3,2,1}
{3,1,2}
{2,1,3}
{2,3,1}
{1,2,3}
{1,3,2}
{2,2,2}

Le reali combinazioni "univoche" che devi trovare sono:

{4,1,1}

{3,2,1}

{2,2,2}

da esse puoi trovarti le altre, basta scambiare di posto i numeri:

ad esempio:

A,B,C  con avremo:

A,B,C
A,C,B
B,A,C
B,C,A
C,A,B
C,B,A

in caso di A=B o A=C o B=C basta eliminare gli "scambi di queste lettere"
Se A=B=C .. eviti tutti gli scambi.

Per trovare le combinazioni "univoche"
Parti da p[0]=n-K+1 (ed il resto tutti 1) come hai fatto tu, poi diminuisci di 1 K fino ad arrivare a p[0]=n/K ed aumenta p[1] di 1, dal primo p[0] (p[0]=n-K+1) abbassi di 2 ed una volta ne aggiungi 2 a p[1], poi aggiungi questo '2' agli indici successivi
p[1]+=1;  P[2]+=1;
La 3° volta
p[1]+=3;  
p[1]+=2;  p[2]+=1;
p[1]+=1;  p[2]+=1; p[3]+=1;
ecc. fino ad arrivare a p[0]=n/K

il resto delle soluzioni si ottengono scambiando di ordine i membri delle soluzioni "univoche"
Comunque sia... il calcolo sarà sempre abbastanza elevato per numeri alti...


Ultima modifica effettuata da il 11/02/2017 alle 14:48
PM Quote