多个字符串的 C++ 笛卡尔积

Question

我将字符串存储在一个向量中：vector<string> ex = {"ab", "cd", "ef"}。现在我需要创建这些字符串的笛卡尔积（向量中字符串的数量，字符串的长度也不固定！）。结果应该是：

  ace
  acf
  ade
  adf
  bce
  bcf
  bde
  bdf

是否已经存在用于此的内置函数，或者您对如何执行实现有任何建议？

笛卡尔积应该使用字符串的单个字母而不是整个字符串！

Answer 1

也许结果可以用 std::accumulate 实现。

需要这种形式的二元运算

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 ;
}

然后调用 std::accumulate(vect.begin(), vect.end(), std::vector(), product)

Answer 2

好的，我想出了一个解决方案。它可能不是最好的，并且肯定可以对代码进行一些改进，但它足以满足我的目的，以防万一有人需要它：

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;

}

Answer 3

我可以使用图书馆提供这种方式 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;
}

我没有对输入数据进行验证。

Answer 4

你可以使用递归。请记住，一旦遇到前一个字符串中的字符，就跳到下一个字符串。

 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);

您的笛卡尔积字符串的最终列表现在存储在向量中：result

多个字符串的 C++ 笛卡尔积

C++ cartesian product of multiple strings

c++

string

cartesian-product