c++ - 从重复的两个列表中生成所有组合

Question

给定 2 个数据列表(列表 A 和列表 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++ 进行编码，但算法适合我。

我已经检查了有关此主题的以下问题。但没有一个像我的问题。

How to find all combinations of sets of pairs - 不允许在第二组重复。

All combinations of pairs within one set - 处理一组。

combinations between two lists? - 不允许在第二组重复。

Finding all possible value combinations between two arrays - 不允许在第二组重复。

An efficient method to generate all possible ways to pair up items in a data set - 处理单集，不允许重复。

我无法想出一个最小的例子，因为我不知道算法。

Answer 1

在我的解决方案中，我创建了一个计数器——一个大小为第一个列表的 vector ，它将迭代器存储在第二个列表中。然后，一切都变得非常容易(甚至不需要太多的代码来实现。)

我的示例代码:

#include <iostream>
#include <list>
#include <vector>

typedef std::list<char> List1;
typedef std::list<int> List2;
typedef std::vector<List2::const_iterator> Counter;

std::ostream& operator << (std::ostream &out, const std::pair<List1&, Counter&> &pair)
{
  Counter::const_iterator iter = pair.second.begin();
  for (const List1::value_type value : pair.first) {
    out << value << **iter++;
  }
  return out;
}

bool count(const List2 &lst2, Counter &counter)
{
  for (size_t i = counter.size(); i--;) {
    if (++counter[i] != lst2.end()) return false;
    counter[i] = lst2.begin();
  }
  return true; // wrap-over
}

int main()
{
  List1 lst1 = { 'a', 'b', 'c' };
  List2 lst2 = { 1, 2 };
  // make/fill counter
  std::vector<List2::const_iterator> counter(lst1.size(), lst2.begin());
  do {
    std::cout << std::pair<List1&, Counter&>(lst1, counter) << '\n';
  } while (!count(lst2, counter));
  // done
  return 0;
}

输出:

a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2

Live Demo on coliru

它就像一个 trip meter 一样简单地工作其中第一个列表提供列的编号和标签，第二个列表提供列的值: