Visualizzazione dei risultati da 1 a 6 su 6

Discussione: [C++] Calcolo combinatorio

  1. #1
    Utente di HTML.it L'avatar di ing82
    Registrato dal
    Sep 2014
    Messaggi
    149

    [C++] Calcolo combinatorio

    Ho la necessità di implementare l'algoritmo che serve a creare le possibili combinazioni di alcuni elementi.
    Il primo pezzo del problema è creare le disposizioni con ripetizione di n elementi a raggruppamenti di k elementi.
    Il numero totale è dato da n elevato alla k.

    Per essere più chiaro, diciamo che voglio le disposizioni con ripetizione di 3 elementi a raggruppamenti di 3, totale 3^3 = 27.
    Se gli elementi sono 0, 1 e 2, ho le seguenti disposizioni
    000 100 200
    001 101 201
    002 102 202
    010 110 210
    011 111 211
    012 112 212
    020 120 220
    021 121 221
    022 122 222

    Prima di passare al codice vero e proprio, cerco di spiegare a parole l'algoritmo, sperando di avere conferma da parte di qualcuno che sia un buon modo di procedere o meno, ed eventualmente come modificare il ragionamento.
    Osservando le disposizioni create, la soluzione che mi è venuta è quella di generare una matrice di n^k righe e k colonne, e poi riempirla tenendo conto che nell'ultima colonna metto la continua ripetizione della serie degli n elementi,
    nella penultima colonna, la ripetizione della serie di n elementi, ma a gruppi di n^delta righe, dove delta indica di quante colonne verso sinistra mi sono spostato rispetto all'ultima colonna, ecc. fino ad arrivare alla prima dove la serie di righe col medesimo valore è pari a n^(k-1).

    Attendo consigli / suggerimenti / miglioramenti ecc, per poi postare il codice, e successivamente passare alla seconda parte del problema.

  2. #2
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,551
    Puoi generarle sequenzialmente partendo da quella precedente senza l'uso di una matrice.
    Parti con un array di dimensione k inizializzato a 0.
    Ad ogni passo aggiungi 1 all'ultima cella. Se questa raggiunge #elementi l'azzeri e aggiungi 1 alla casella che la precede andando avanti così fino a che non arrivi ad azzerare la cella 0, in quel momento hai finito.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  3. #3
    Utente di HTML.it L'avatar di ing82
    Registrato dal
    Sep 2014
    Messaggi
    149
    Quote Originariamente inviata da Scara95 Visualizza il messaggio
    Puoi generarle sequenzialmente partendo da quella precedente senza l'uso di una matrice.
    L'uso della matrice è per il fatto che una volta generate le combinazioni devono poi essere usate.

    Quote Originariamente inviata da Scara95 Visualizza il messaggio
    Parti con un array di dimensione k inizializzato a 0.
    Ad ogni passo aggiungi 1 all'ultima cella. Se questa raggiunge #elementi l'azzeri e aggiungi 1 alla casella che la precede andando avanti così fino a che non arrivi ad azzerare la cella 0, in quel momento hai finito.
    Una soluzione del genere credo di averla già trovata in giro (non per sminuire il valore della risposta, ma perchè prima di buttarmi in miei ragionamenti speravo di trovare la pappa pronta pensando che fosse un problema ricorrente e già risolto), ma non so perchè non la avevo capita.
    ora mi sembra più utilizzabile, e probabilmente questo mi toglie d'impaccio anche per la seconda parte del problema.
    Sistemo il codice e poi lo posto.
    Grazie

  4. #4
    Utente di HTML.it
    Registrato dal
    Mar 2001
    Messaggi
    567
    secondo me le matrici rappresentano una limitazione in quanto la memoria di un calcolatore non è infinita. Se il numero delle combinazioni dovessero crescere di molto, ci si scontra poi coi limiti fisici della macchina che esegue l'algoritmo.

  5. #5
    Utente di HTML.it L'avatar di ing82
    Registrato dal
    Sep 2014
    Messaggi
    149
    Quote Originariamente inviata da misterx Visualizza il messaggio
    secondo me le matrici rappresentano una limitazione in quanto la memoria di un calcolatore non è infinita. Se il numero delle combinazioni dovessero crescere di molto, ci si scontra poi coi limiti fisici della macchina che esegue l'algoritmo.
    Grazie per l'osservazione, ma faccio presente che stai parlando con un programmatore per hobby, quindi certe cose per me non sono così scontate...

    Le combinazioni devono essere create a partire da una coppia di valori double, per quanto riguarda il numero di elementi k credo che difficilmente superi la decina, anche se non si sa mai e anche se in realtà poi subentreranno altre problematica che faranno lievitare il numero di combinazioni.

    Per ora mi accontenterei di capire dove sta il limite, se posso prevederlo, e quindi mandare un avviso o roba simile per non andare in crash prima dell'esecuzione dell'algoritmo (tanto sto programmando per me stesso...)

    Grazie

  6. #6
    Utente di HTML.it L'avatar di ing82
    Registrato dal
    Sep 2014
    Messaggi
    149
    Ho scritto qualche riga di codice che sembra funzionare, ma probabilmente pu� essere migliorata, ma ci penseremo.
    L'ho fatta con la possibilit� che non siano da creare semplicemente le disposizioni con ripetizione di numeri interi, ma di qualsiasi cosa: a me, per la prima parte del problema, servono le disposizioni di una coppia di valori double.
    Ecco la funzione (scusate per la formattazione del codice, ma quando ho incollato qui, e' andato tutto per aria, ma ho sistemato in qualche modo...):
    codice:
    template<classT>
    std::vector<std::vector<T>>makeDispositionWithRepetitions(std::vector<T>& value,const int& k)
    {
     std::vector<std::vector<T>> matrix;
     std::vector<int> temp(k,0); 
      unsigned int n = value.size();//numerodeglielementichedarannooriginealledisposizioni 
     std::vector<T> new_row(k,value[0]);
     bool condizione=true;//diventafalsequandol'elementodellaprimacolonnavienemessoazero 
     matrix.push_back(new_row);//inseriscolaprimariganellamatrice 
     while(condizione)
     {
      if(temp[k-1]+1==n)
      {
       temp[k-1]=0;//rimettoazerol'indicedell'elementodell'ultimacolonna 
       boolstop=true;
       unsignedintj=1;
       while(stop)
       {
        if(temp[k-1-j]+1==n)
        {
         if(j+1==k)
         {
          std::cout<<"stocambiandoinfalselavariabilecondizione"<<std::endl;
          condizione=false;
          stop=false;
         }
         else
         {
          temp[k-1-j]=0;
          j=j+1;
         }
        }
        else
        {
         temp[k-1-j]=temp[k-1-j]+1;
         stop=false;
        }
       }
      }
      else
      {
       temp[k-1]=temp[k-1]+1;
      }
      //con questo ciclo creo la nuova riga della matrice con gli elementi che effettivamente devono
      //essere combinati tra loro
      for(unsignedintt=0;t<k;t++)
      {
       new_row[t]=value[temp[t]];
      }
      if(condizione)
      {
       matrix.push_back(new_row);
      }
     }
      returnmatrix;
    }
    Impostato cosi' il problema credo che mi diventi gestibile anche la seconda parte dello stesso, in quanto le disposizioni da creare sono di n elementi di cui n1 che possono assumere una coppia di valori, mentre i rimanenti n2 una diversa coppia di valori, per cui dovrei solamente modificare il ciclo for che assegna i valori corretti alla nuova riga, prendendo per i primi n1 la prima coppia di valori, per i rimanenti n2 la secondo coppia di valori (dovro' quindi aggiungere un secondo vettore e un secondo numero di elementi come parametri passati alla funzione).

    spero si rifaccia vivo misterx per darmi qualche indicazione su come affrontare, o meglio, arginare, il problema dell'uso della memoria.

  7. #7
    Utente di HTML.it L'avatar di ing82
    Registrato dal
    Sep 2014
    Messaggi
    149
    Ultima modifica di ing82; 07-02-2018 a 13:02 Motivo: messaggio partito doppio, uguale al precedente, non sapendo come elminarlo, ho messo l'emoticon...Scusate!

  8. #8
    Utente di HTML.it L'avatar di ing82
    Registrato dal
    Sep 2014
    Messaggi
    149
    Ho tenuto conto del consiglio dato da Scara95, dicendo di far variare l'ultimo elemento e via via retrocedere fino alla prima colonna.
    Con questo sistema, sono riuscito a risolvere le prime due parti del problema.
    Il codice qui riportato, permette di creare le disposizioni con ripetione, di due gruppi di elementi, di numeri diversi da raggruppare in due numeri diversi: se qualcuno ha miglioramenti da fare, ben accetti.
    Con un esempio spero di essere piu' chiaro:
    significa che posso creare le n1^k1 * n2^k2 disposizioni con ripetizione dei parametri passati alla funzione.
    se n1 = 2 e i valori sono 'a' e 'b', e k1=3,
    se n2 = 3 e i valori sono '0' , '1' e '2', e k2=2,
    le disposizione che dovrei ottenere sono 2^3 * 3^2 = 8 * 9 = 72
    (me le appiccica tutte assieme, ma vanno lette a gruppi di 5 (k1+k2) )

    a a a 0 0 // a a b 0 0 // a b a 0 0
    a a a 0 1 // a a b 0 1 // a b a 0 1
    a a a 0 2 // a a b 0 2 // a b a 0 1
    a a a 1 0 // a a b 1 0 // a b a 1 0
    a a a 1 1 // a a b 1 1 // a b a 1 1
    a a a 1 2 // a a b 1 2 // a b a 1 2
    a a a 2 0 // a a b 2 0 // a b a 2 0
    a a a 2 1 // a a b 2 1 // a b a 2 1
    a a a 2 2 // a a b 2 2 // a b a 2 2


    a b b 0 0 // b a a 0 0 // b a b 0 0
    a b b 0 1 // b a a 0 1 // b a b 0 1
    a b b 0 2 // b a a 0 2 //b a b 0 1
    a b b 1 0 // b a a 1 0 // b a b 1 0
    a b b 1 1 // b a a 1 1 // b a b 1 1
    a b b 1 2 // b a a 1 2 //b a b 1 2
    a b b 2 0 // b a a 2 0 // b a b 2 0
    a b b 2 1 // b a a 2 1 // b a b 2 1
    a b b 2 2 // b a a 2 2 // b a b 2 2


    b b a 0 0 // b b b 0 0
    b b a 0 1 // b b b 0 1
    b b a 0 2 // b b b 0 1
    b b a 1 0 // b b b 1 0
    b b a 1 1 // b b b 1 1
    b b a 1 2 // b b b 1 2
    b b a 2 0 // b b b 2 0
    b b a 2 1 // b b b 2 1
    b b a 2 2 // b b b 2 2




    codice:
    template<class T>
    std::vector<std::vector<T>> makeDispositionWithRepetitions_multi(std::vector<T>& value1, const unsigned int& k1, std::vector<T>& value2, const unsigned int& k2)
    {
      std::vector<std::vector<T>> matrix;
      //mettere controllo che il vettore degli elementi value sia valido, cioè non sia vuoto
      //mettere controllo che k sia di valore maggiore o uguale a 1
      //se le condizioni sono rispettate, vado avanti
      unsigned int k = k1 + k2;
      std::vector<int> temp(k,0);
    
      unsigned int n = value1.size();//numero degli elementi che daranno origine alle disposizioni
      //do per scontato che il numero di valori sia identico per entrambi i vettori
    
      unsigned int n1 = value1.size();
      unsigned int n2 = value2.size();
    
      std::vector<T> new_row;
      //cilco for per inizializzare la prima riga coi primi k1 valori uguali a value1[0], gli altri k2 valori uguali a value2[0]
      for(unsigned int pippo = 0; pippo< k; pippo++)
      {
          if(pippo<k1)
          {
              new_row.push_back(value1[0]);
          }
          else
          {
              new_row.push_back(value2[0]);
          }
      }
    
      bool condizione = true;//diventa false quando l'elemento della prima colonna viene messo a zero
    
      matrix.push_back(new_row);//inserisco la prima riga nella matrice
    
      while (condizione)
      {
        if(temp[k-1] + 1 == n2)
        {
          temp[k-1] = 0;//rimetto a zero l'indice dell'elemento dell'ultima colonna
          //std::cout<<"Ho messo a zero l'ultima colonna";
          bool stop = true;
          unsigned int j = 1;
          while(stop)
          {
            if(j<k2)
            {
              if(temp[k-1-j] + 1 == n2)
              {
                 if(j + 1 == k)
                 {
                     condizione = false;
                     stop = false;
                 }
                 else
                 {
                  temp[k-1-j] = 0;
                  j = j + 1;
                 }
              }
              else
              {
                  temp[k-1-j] = temp[k-1-j] + 1;
                  stop = false;
              }
            }
            else if(j>=k2)
            {
    
              if(temp[k-1-j] + 1 == n1)
              {
                 if(j + 1 == k)
                 {
                     condizione = false;
                     stop = false;
                 }
                 else
                 {
                  temp[k-1-j] = 0;
                  j = j + 1;
                 }
              }
              else
              {
                  temp[k-1-j] = temp[k-1-j] + 1;
                  stop = false;
              }
            }
    
          }
        }
        else
        {
          temp[k-1] = temp[k-1] + 1;
        }
        for(unsigned int t = 0; t<k; t++)
        {
          if(t<k1)
          {
            new_row[t] = value1[temp[t]];
          }
          else
          {
            new_row[t] = value2[temp[t]];
          }
        }
        if(condizione)
        {
          matrix.push_back(new_row);
        }
        /*for(unsigned int i=0; i<matrix.size(); i++)
        {
          for(unsigned int j=0; j<matrix[0].size(); j++)
          {
            //std::cout<<std::setprecision(2);
            std::cout<<matrix[i][j]<<"  ";
          }
          std::cout<<std::endl;
        }
        getchar();*/
    
      }
    
      return matrix;
    }
    Ultima modifica di ing82; 12-02-2018 a 12:06

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2018 vBulletin Solutions, Inc. All rights reserved.