C++ cartesian product of multiple strings

Question

I have strings stored in a vector as such: vector<string> ex = {"ab", "cd", "ef"}. Now I need to create the cartesian product of these strings (number of strings in the vector, nor the length of the strings is fixed!). The result should be:

  ace
  acf
  ade
  adf
  bce
  bcf
  bde
  bdf

Is there a build-in function that exists already for this, or do you have any advice how to perform the implementation?

The single letters of the strings should be used for the cartesian product not the entire string!

If the answer (as I suspect) is "no," do you have a follow-up question? — Scott Hunter, May 26 '15 at 19:58
As for advice: this looks like a job for recursion. But you'll need to specify what form you want the result in (printout? another vector of strings? something else?). — Scott Hunter, May 26 '15 at 20:01
possible duplicate of [How can I create cartesian product of vector of vectors?](http://stackoverflow.com/questions/5279051/how-can-i-create-cartesian-product-of-vector-of-vectors) — Ami Tavory, May 26 '15 at 20:01
No, there isnt such a function. But it should not be that hard to generate what you want using recursion (but be careful here with too long strings... recursion is a two-sided-sword) — Nidhoegger, May 26 '15 at 20:05

score 2 · Answer 1 · answered May 29 '15 at 07:41

I can offer this way using the library https://cpplinq.codeplex.com/

#include <iostream>
#include <vector>
# include <algorithm>
# include <iterator>
# include <string>
# include <tuple>
# include <functional>
# include <cmath>
#include "cpplinq.hpp"
using namespace cpplinq;

std::vector<std::string> simpleTransform(const std::vector<std::string> &ex);
int main()
{
std::vector<std::string> ex1(3);
ex1[0]="ab";
ex1[1]="cd";
ex1[2]="ef";

auto VS = simpleTransform(ex1);
std::copy(VS.begin(),VS.end(),std::ostream_iterator<std::string>(std::cout,"\n"));

return 0;
}

std::vector<std::string> simpleTransform(const std::vector<std::string> &ex)
{
size_t N = ex.size();
size_t M = ex[0].size();
std::vector<std::string> VS(pow(M,N)); 
size_t count=0;

std::function<void(size_t,std::vector<size_t>)> Var=
    [&](size_t ind,std::vector<size_t> vec)
    {
    if(ind==0) 
        {
        std::string r;
        r.resize(N);
        for(size_t j=0;j<N;j++)
             r[j] = ex[j][vec[j]-1];

        VS[count] =r; 
        count++;
        return;
        }
    else
        {
        std::vector<size_t> newvec(vec);
        auto temp = N-ind+1;
        newvec.resize(temp);
        range(1,M)>>for_each([&](int const & j){
        newvec[temp-1]=j;
        Var(ind-1,newvec);});
        }
    };
Var(N,std::vector<size_t>());

return VS;
}

I didn't do validation of input data.

wasp256 · Accepted Answer · 2015-05-29T08:55:24.610

Ok I came up with a solution. It might not be the best one and there are for sure some improvements of the code possible but its enough for my purposes and in case someone needs it too:

vector<string> getProducts(vector<string> s) {
int combinations = 1;
vector<string> res;
for (unsigned int i=0; i<s.size(); i++) {
    combinations *= s.at(i).length();
}

for (unsigned int i=0; i<s.size(); i++) {
    string cur = s.at(i);
    int div = combinations / cur.length();
    int count = 0;
    for (unsigned int ch=0; ch<cur.length(); ch++) {
        for (int len=0; len<div; len++) {
            if (i==0) {
                res.push_back(string(cur.substr(ch, 1)));
            } else {
                string tmp = res.at(count);
                tmp.append(string(cur.substr(ch,1)));
                res.at(count) = tmp;
            }
            count++;
        }


        if ((ch == cur.length()-1) && (count <= res.size()-1) && i>0) {
            ch = -1;
        }
    }
    combinations = div;
}

return res;

}

score 0 · Answer 3 · edited Feb 02 '22 at 05:03

You can use recursion. Just remember to hop on to the next string as soon as you encounter a character in the previous string.

 void backtrack(int i, string cur_str, vector<string> ex, vector<string> &result)
    {
        //If appended string reaches the end, push to result and return;
        if(cur_str.size() == ex.size())
           {
              result.push_back(cur_str);
              return;
           }
        
        //Backtrack: Keep moving to next string recursively
        for(char c : ex[i])
            backtrack(i+1, cur_str+c, ex, result);
        
    }
 
 //Initialise a vector, result will stored here
  vector<string> result;

 //Call the recursive function for the first time starting at 0th index, 
 //and an empty string that will keep adding characters on the go
 backtrack(0, "", digits, result);

Your final list of cartesian product strings are now stored in the vector: result

marom · Answer 4 · 2015-05-26T20:26:04.883

-1

May be the result is achievable with std::accumulate.

One needs a Binary operation of this form

std::vector<string> product(const std::vector<string> &init, string value)
{
    std::string result ;
    for (auto ch : value)
        if (init.empty())
            result.push_back(string(1, ch)) ;
        else 
            for (auto str : init)
                result.push_back(str + string(1, ch)) ;
    return result ;
}

then call std::accumulate(vect.begin(), vect.end(), std::vector(), product)

edited May 26 '15 at 20:26

answered May 26 '15 at 20:06

marom

5,064
10
14

It's not compilable, what is std::accumulator? What is `prod`? – wasp256 May 26 '15 at 20:16
std::accumulate is a function of standard header. prod is a typo.. I corrected it into product – marom May 26 '15 at 20:19
I included `` now -> still get a `function accumulate could not be resolved`, the function gives me errors `No return`, `result.push(...) -> invalid arguments` – wasp256 May 26 '15 at 20:23
May be now is better, in case of other compile time errors I leave them as exercise... :-) – marom May 26 '15 at 20:27

C++ cartesian product of multiple strings

4 Answers4

Linked