Arrays Cartesian Product with C++

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


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:


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:


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:


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





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
        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 = ';';
        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)
            stringstream ss(line);
            // La linea del file deve terminare con un enter...
            // File line must finish with enter...
                    } 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
                } 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
      // Provo a mischiare i record...Quando trovo che il size è uno, allora ho finito.
      // Try to mix the records...When size = 1 --> finish!
          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;
              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];
                          } 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
           // .... insert - inserisco
                } 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
          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
                  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
          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;
// 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;


FileDescriptionFile sizeDownloadsCreated
Download this file ( program to generate the cartesian product of arrays of variable's values from input file79 kB5042013-01-12 17:47