从两个重复列表生成所有组合
从两个重复列表生成所有组合
提问于 2018-07-31 11:35:28
给定两个数据列表(list A & list B)，我需要一个算法来生成所有可能的组合C，以便在每个组合中：
A的所有项目都必须存在，排序不重要(例如，abc与cba相同)- 来自
B的确切1项必须在A的每个项目之后出现 - 可以重复
B中的项
示例1
A = {a, b, c}
B = {1, 2}答案：
a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2示例2
A = {a, b}
B = {1, 2, 3}答案：
a1b1
a1b2
a1b3
a2b1
a2b2
a2b3
a3b1
a3b2
a3b3我能遵循什么算法来生成这个答案？谢谢。我看到了模式，但无法将其转换为代码。我将使用C++进行编码，但算法将对我有效。
我已经检查了关于这个主题的以下问题。但没有一个是我的问题。
如何找到所有对的组合 -不允许在第二盘重复。
一组中所有对的组合 -处理一套。
两个列表之间的组合？ -不允许在第二盘重复。
在两个数组之间查找所有可能的值组合 -不允许在第二盘重复。
生成数据集中项对的所有可能方法的有效方法 -处理单组，不允许重复。
我想不出一个最小的例子，因为我不知道算法。
回答 3
Stack Overflow用户
发布于 2018-07-31 12:30:55
这些都是变相的B元素的重复排列。如果您只查看来自B的元素(例如来自OP)，那么我们有：
111
112
121
122
211
212
221
222这正是B的重复排列。A中的元素被简单地填充以获得所需的结果。
template <typename typeVec1, typename typeVec2>
void customPerms(typeVec1 a, typeVec2 b) {
int r = a.size(), n = b.size();
int r1 = r - 1, n1 = n - 1;
std::vector<int> z(r, 0);
int numRows = (int) std::pow(n, r);
for (int i = 0; i < numRows; ++i) {
for (int j = 0; j < r; ++j)
std::cout << a[j] << b[z[j]];
std::cout << std::endl;
for (int k = r1; k >= 0; --k) {
if (z[k] != n1) {
++z[k];
break;
} else {
z[k] = 0;
}
}
}
}我们称它为：
#include <iostream>
#include <cmath>
#include <vector>
int main() {
std::cout << "Example 1 : " << std::endl;
std::vector<std::string> a1 = {"a", "b", "c"};
std::vector<int> b1 = {1, 2};
customPerms(a1, b1);
std::cout << "\nExample 2 : " << std::endl;
std::vector<char> a2 = {'a', 'b'};
std::vector<int> b2 = {1, 2, 3};
customPerms(a2, b2);
return 0;
}这是输出：
Example 1 :
a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2
Example 2 :
a1b1
a1b2
a1b3
a2b1
a2b2
a2b3
a3b1
a3b2
a3b3下面是一个有用的示例：https://ideone.com/OUv49P
Stack Overflow用户
发布于 2018-07-31 13:15:52
这方面有许多可能的解决办法。我正在用递归调用构建一个字符串：
#include <vector>
#include <iostream>
#include <string>
using charVec = std::vector<char>;
using intVec = std::vector<int>;
void printEl(const std::string& start, charVec::const_iterator it, const charVec::const_iterator& endIt, const intVec& iV)
{
if (it == endIt)
{
std::cout << start << "\n";
return;
}
for (const auto& iVel : iV)
{
printEl(start + *it + std::to_string(iVel), it + 1, endIt, iV);
}
}
void printComb(const charVec& cV, const intVec& iV)
{
printEl("", cV.cbegin(), cV.cend(), iV);
}
int main()
{
charVec A1{ 'a', 'b', 'c' };
intVec B1{ 1, 2 };
printComb(A1, B1);
std::cout << "next example: \n";
charVec A2{ 'a', 'b' };
intVec B2{ 1, 2, 3 };
printComb(A2, B2);
}Stack Overflow用户
发布于 2018-07-31 13:42:17
实际上，有许多解决方案是可能的，这里是我的简单递归解决方案，非常类似于possible的解决方案，但没有生产代码的 pretty 。
void permute_helper(vector<string>& A, vector<string>& B, int ii, string curr)
{
if(ii == A.size())
{
cout << curr << endl;
return;
}
for(int i = 0; i < B.size(); ++i) permute_helper(A, B, ii + 1, curr + A[ii] + B[i]);
}
void permute(vector<string>& A, vector<string>& B)
{
permute_helper(A,B,0,"");
}
int main() {
vector<string> A = {"a","b","c"};
vector<string> B = {"1","2"};
permute(A,B);
return 0;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51612440
复制相关文章
相似问题
腾讯云开发者
