Articoli

Arrays Cartesian Product with C++

Consider N arrays containing KN values each one; in other words:

 

x1x2...xN
a1 b1 ... N1
a2 b2 ... N2
... ... ... ...
aK1 bK2 ... NKN

 

In the general case, we have: K1 != K2 != ... != KN. The total number of combinations is: K1 * K2 *...* KN. An example:

 

x1x2x3
a1 b1 c1
a2 b2
a3 b3

The number of combinations is 3*3*1 = 9 and the list of all combinations is the following:

 

x1x2x3
a1 b1 c1
a1 b2 c1
a1 b3 c1
a2 b1 c1
a2 b2 c1
a2 b3 c1
a3 b1 c1
a3 b2 c1
a3 b3 c1

 

The following C++ program generate all the combinations starting from the arrays written into a file in the form:

a1;a2;a3;a4
b1;b2;b3;b4;b5;b6
1;2;3
10;20;30;40;50;60;70
100;200;300;400
AAA;BBB;CCC;DDD;EEE

where each row represents the value's list of each variable, separated by ";" or whathever 1-char separator. The output is in the form:

 

a1;b1;1;10;100;AAA
a1;b1;1;10;100;BBB
a1;b1;1;10;100;CCC
a1;b1;1;10;100;DDD
a1;b1;1;10;100;EEE
a1;b1;1;10;200;AAA
a1;b1;1;10;200;BBB
a1;b1;1;10;200;CCC
a1;b1;1;10;200;DDD
a1;b1;1;10;200;EEE

 

 

where in the first column there are the values of the first variable, in the second colum the values of the second variables and so on. There are no variable names in the input file and no headers in the output.

The program takes as input two parameters:

  1. Mandatory input file name, filled with the variables values as specified above
  2. Optional 1-char variable values separator. The default separator is ";". If you use a separator long more than one char, just the fist char is considered.

The usage is:

Windows: ProdCart.exe filename [1-char separator]
Unix:    ./prodcart filename [1-char separator]

For example:

ProdCart.exe c:\Normal.txt
ProdCart.exe c:\OtherSep * (assuming that the separator among the variable's values is *)

 

The output is printed on the standard output (video), but you can use the "pipe" operators (> or >>) to redirect the output to a file.

From the attach at the end of this article, you can download the source, executable ProdCart.exe for windows, executable prodcart for *ix, readme.html file and some input file I used to test the program, as example. In details:

  • Overflow.txt input file with too many variables and values that cause a (managed) memory overflow
  • Limit.txt input file that generate 23.887.872 combinations,that is the limit before memory overflow (at least on my PC)
  • Normal.txt input file that generate 1536 combinations, that is a "normal" value

 

#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <deque>
#include <vector>
using namespace std;
int main(int argc,char *argv[])
{
    //Controllo il numero dei parametri
    //Verify parameters' number
    if(argc==1){
        cout << "Usage:" << endl;
        cout << "1)Assuming that the separator is ; for variables' values" << endl;
        cout << "      ProdCart <filename>" << endl;
        cout << "2)Passing the separator as second parameter. In the example pass * as separator for variables' values" << endl;
        cout << "      ProdCart <filename> *" << endl;
        cout << "More details on README file" << endl;
        return 0;
    }
    //Se c'è il secondo parametro, è il carattere di separazione (primo carattere)
    //If exixst 2-nd parameter, this is the separator (just 1-st char)
    char SEP = ';';
    if(argc==3){
        SEP = argv[2][0];
    }
    //Imposto i parametri
    //Variable definition
    string line,item,strTemp;
    deque< vector<string> > deq;
    vector<string> rowMix;
    long int count = 0;
    //Definizione funzioni ausiliarie
    //Auxiliary function definition
    bool verifyAvailableMemory();
    //Input file
    ifstream myfile(argv[1]);
    if (myfile.is_open())
    {
      while ( myfile.good() )
      {
          // Creo una nuova riga
          // Create new row
          vector<string> row;
          // Leggo la nuova linea dal file e la carico nello stringstream
          // Read new line and load into the stringstream
          getline (myfile,line);
          // Se la linea non è vuota...gli spazi vengono considerati validi
          // If line not empty... (spaces are considered valid)
          if(!line.empty()){
            stringstream ss(line);
            // La linea del file deve terminare con un enter...
            // File line must finish with enter...
            try{
                while(getline(ss,item,SEP)){
                    if(verifyAvailableMemory()){
                        row.push_back(item);
                    } else {
                        cout << "001-Error allocating memory while reading file. File too big or not correctly formatted !" << endl;
                        return 0;
                    }
                }
            }catch (exception& e){
              cout << "002-The following error occurred: " << e.what() << endl;
              return 0;
            }
            // Inserisco la nuova riga nella deque
            // Insert new row in deque
            try{
                if(verifyAvailableMemory()){
                    deq.push_back(row);
                } else {
                    cout << "003-Error allocating memory while creating deque. Too many combinations !" << endl;
                    return 0;
                }
            } catch (exception& e){
                cout << "004-The following error occurred: " << e.what() << endl;
                return 0;
            }
          } // Close empty line - Chiusura line vuota
      } // Close while - Chiudo while
      // Close file - Chiusura file
      myfile.close();
      // Provo a mischiare i record...Quando trovo che il size è uno, allora ho finito.
      // Try to mix the records...When size = 1 --> finish!
      try{
          cout << endl;
          cout << "Started! Wait... when the counter is 1 the combinations start print out. Depending n the numbers " ;
          cout << "of combinations, this operation should take long time! It's possible to interrupt the program with Control+C";
          cout << endl << endl;
          while(deq.size()>1){
              strTemp.clear();
              rowMix.clear();
              for(unsigned long long i=0; i<deq[0].size(); ++i){
                  for (unsigned long long j=0; j<deq[1].size(); ++j){
                      strTemp = deq[0][i] + SEP + deq[1][j];
                      try{
                          if(verifyAvailableMemory()){
                              rowMix.push_back(strTemp);
                          } else {
                              cout << "005-Error allocating memory while mixing records. Too many combinations !" << endl;
                              return 0;
                          }
                      } catch(exception& e){
                          cout << "006-The following error occurred: " << e.what() << endl;
                          return 0;
                      }
                  } // Close 2-nd for - Chiudo 2-do for
              } // Close 1-st for - Chiudo 1-mo for
           // Devo eliminare i due record di testa da deq e sostituirli con quello calcolato deqMix
           // Remove 2 records in the head from deque and replace with the deqMix just calculated
           // .... remove - elimino
           deq.pop_front();
           deq.pop_front();
           // .... insert - inserisco
           try{
                if(verifyAvailableMemory()){
                 deq.push_front(rowMix);
                } else {
                    cout << "007-Error allocating memory while creating record. Too many combinations !" << endl;
                    return 0;
                }
           } catch (exception& e){
                 cout << "008-The following error occurred: " << e.what() << endl;
                 return 0;
           }
           cout << "Counter = " << deq.size() << endl;
          } // End while cycle - Fine ciclo while
      } catch (exception& e) {
           cout << "009-The following error occurred: " << e.what() << endl;
           return 0;
      }
      // Stampo il vettore mischiato
      // Print the mixed record
      try{
          for(unsigned long long i=0; i<deq.size(); ++i){
              for (unsigned long long j=0; j<deq[0].size(); ++j){
                  // Incremento il contatore delle combinazioni...
                  // Update combinations counter
                  count++;
                  cout  << deq[0][j] << endl;
              }
           }
      } catch (exception& e){
          cout << "010-The following error occurred: " << e.what() << endl;
          return 0;
      }
      //Stampo il numero di combinazioni totali
      //Print the total combinations number
      cout << "# of combinations: " << count <<endl;
      //Controllo se il numero di combinazioni e zero, il file è vuoto
      //If combinations number is 0 the file could be empty
      if(count==0){
          cout << "Mhhh.. strange! # of combinations = 0; should the input file be empty ?" << endl;
      }
    } // End file open control - Fine controllo apertura file
    else cout << "011-Unable to open file: " << argv[1] << endl;
    return 0;
}
// END MAIN
//*****************************************
// Auxiliary functions
//*****************************************
// Verify if available memory exist...
bool verifyAvailableMemory(){
    int *pi = new (nothrow) int[16384];
    if(pi == NULL)
    {
       cout << "V1-Could not allocate memory" << endl;
       return false;
    }
    delete pi;
    return true;
}

 

Allegati:
FileDescrizioneDimensione del FileDownloadsCreato
Scarica questo file (ProdCart.zip)ProdCartC++ program to generate the cartesian product of arrays of variable's values from input file79 kB3732013-01-12 17:47

Aggiungi commento


Codice di sicurezza
Aggiorna

Copyright © 2017 Berta Danilo. Tutti i diritti riservati.
Joomla! è un software libero rilasciato sotto licenza GNU/GPL.