从 2D 字符串向量中获取标记组合

Question

我有一个 2D 向量

vecTokens

，其中包含字符串标记的子向量。我需要一个字符串的结果向量，其大小 =

vecTokens

中所有子向量大小相乘的结果，其中每个元素必须是由“|”分隔的字符串标记的组合如向量

finalResults

所示。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<vector<string>> vecTokens
    {
        {"1", "2", "3", "4"}, // 4 tokens
        {"101", "102", "103"}, // 3 tokens
    };
    
    //Size is 4*3 = 12
    vector<string> finalResults
    {
        "1|101", "1|102", "1|103",
        "2|101", "2|102", "2|103",
        "3|101", "3|102", "3|103",
        "4|101", "4|102", "4|103"
    };
    return 0;
}

如果修改

vecTokens

以包含更多元素，例如

vector<vector<string>> tokens
{
    {"1", "2", "3", "4"}, // 4 tokens
    {"101", "102", "103"}, // 3 tokens
    {"6", "7"}, // 2 tokens
};

finalResults

应该看起来像

//Size is 4*3*2 = 24
vector<string> finalResults
{
    "1|101|6", "1|101|7", "1|102|6", "1|102|7", "1|103|6", "1|103|7",
    "2|101|6", "2|101|7", "2|102|6", "2|102|7", "2|103|6", "2|103|7",
    "3|101|6", "3|101|7", "3|102|6", "3|102|7", "3|103|6", "3|103|7",
    "4|101|6", "4|101|7", "4|102|6", "4|102|7", "4|103|6", "4|103|7",
};

目前我陷入了应该采用什么方法来实现结果的困境。任何执行类似操作的标准算法也会有所帮助。

Answer 1

主要观察结果向量的大小以及组合每个元素的元素索引。

让我们用

v_1, ..., v_k

来表示你的向量，它们的大小分别为

n_1, ... n_k

。

大小是乘法

n_1 * ... * n_k

，对于每个

0 <= i < size

，元素

i

由元素

(i%(n_2 * ... * n_k), i%(n_3 * ... * n_k),..., i%1

组合而成。

在第二个示例中，您可以看到，换句话说，第一个元素的标识每

6

连续元素都会更改，第二个元素每

2

连续元素都会更改，第三个元素每

1

都会更改。

因此，要实现此目的，您可以简单地编写类似的内容

int size; // n_1 * ... * n_k
vector<int> sizes; // (n_1, ..., n_k)
vector<string> res(size);
for (int i = 0 ; i < size ; i ++) {
  vector<int> index_tuple = compute_index_tuple(i, sizes);
  res[i] = concatenate_with_bars(vecTokens, index_tuple);
}

其中

compute_index_tuple

执行上述所有模数运算，

concatenate_with_bars

从

index_tuple[k]

中获取

vecTokens[k]

元素并将其与

|

字符连接起来。

Answer 2

借助 C++23

views::cartesian_product

和

views::transform

，您可以

auto finalResults = std::views::cartesian_product(vecTokens[0], 
                                                  vecTokens[1], 
                                                  vecTokens[2])
                  | std::views::transform([](auto tuple) {
                      return std::apply([](auto first, const auto&... rest) {
                        return ((first += ('|' + rest)), ...);
                      }, tuple);
                  });

Answer 3

您可以根据这些值构建一个图表，并运行 DFS（对于第一行中的所有节点）来获取您想要的笛卡尔积字符串。

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <sstream>

struct GraphNode
{
    std::string val;
    std::vector<int> neighbor_indices;   // Directed edges
};

class Graph
{
    std::vector<GraphNode> nodes;
    std::map<std::string, int> node_index;
    std::vector<int> start_set; // set of ids for which dfs must be run

    void dfs(int start_i, std::vector<std::string>& v)
    {
        using P = std::pair<int, std::string>;

        std::stringstream ss;
        std::stack<P> s;
        s.push({start_i, ""});
        while (!s.empty())
        {
            auto [i, str] = s.top();
            s.pop();

            const auto& node = nodes[i];
            str += node.val;

            if (node.neighbor_indices.empty())
            {
                v.push_back(str);
                continue;
            }

            str += '|';

            for (int n : node.neighbor_indices)
            {
                s.push({n, str});
            }
        }
    }
public:
    Graph(const std::vector<std::vector<std::string>>& v)
    {
        for (size_t i = 1; i < v.size(); i++)
        {
            const auto& v1 = v[i - 1];
            const auto& v2 = v[i];
            
            // construct nodes if not present
            for (const auto& val : v1)
            {
                if (node_index.find(val) == node_index.end())
                {
                    GraphNode new_node{val};
                    nodes.push_back(new_node);
                    node_index[val] = nodes.size() - 1;
                }
            }

            // construct nodes if not present
            for (const auto& val : v2)
            {
                if (node_index.find(val) == node_index.end())
                {
                    GraphNode new_node{val};
                    nodes.push_back(new_node);
                    node_index[val] = nodes.size() - 1;
                }
            }

            // add directed edge from v1 nodes to v2 nodes
            for (const auto& val1 : v1)
            {
                int val1_index = node_index[val1];
                for (const auto& val2 : v2)
                {
                    int val2_index = node_index[val2];

                    nodes[val1_index].neighbor_indices.push_back(val2_index);
                }
            }
        }

        for (const auto& val : v[0])
        {
            start_set.push_back(node_index[val]);
        }
    }

    void print()
    {
        for (const auto& graphNode : nodes)
        {
            std::cout << graphNode.val << ": ";
            for (int i : graphNode.neighbor_indices)
            {
                std::cout << nodes[i].val << ' ';
            }
            std::cout << '\n';
        }
    }

    std::vector<std::string> get_cartesian_product()
    {
        std::vector<std::string> result;
        
        for (int i : start_set)
        {
            dfs(i, result);
        }

        return result;
    }
};

int main()
{
    std::vector<std::vector<std::string>> vecTokens
    {
        {"1", "2", "3", "4"}, // 4 tokens
        {"101", "102", "103"}, // 3 tokens
    };

    std::vector<std::vector<std::string>> vecTokens2
    {
        {"1", "2", "3", "4"}, // 4 tokens
        {"101", "102", "103"}, // 3 tokens
        {"6", "7"}, // 2 tokens
    };

    Graph one{vecTokens};
    //one.print();
    for (const auto& s : one.get_cartesian_product())
    {
        std::cout << s << '\n';
    }

    std::cout << "---------------------------------\n";
    Graph two{vecTokens2};
    //two.print();
    for (const auto& s : two.get_cartesian_product())
    {
        std::cout << s << '\n';
    }
    
    return 0;
}