Generating all combinations from two lists with repetition

Question

Given 2 lists of data (list A & list B) I need an algorithm to generate all possible combination C such that in each combination:

• All items of A must be present, ordering doesn't matter (e.g., abc is same as cba)
• Exactly 1 item from B must be present after each item from A
• Items from B can be repeated

Example 1

A = {a, b, c}
B = {1, 2}

Answer:

a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2

Example 2

A = {a, b}
B = {1, 2, 3}

Answer:

a1b1
a1b2
a1b3
a2b1
a2b2
a2b3
a3b1
a3b2
a3b3

What algorithm can I follow to generate this answer? Thanks. I see the pattern, but unable to translate it to code. I'll be coding in C++, but an algorithm will work for me.

I've checked the following questions on SO about this topic. But none is like my problem.

How to find all combinations of sets of pairs - doesn't allow repetition on 2nd set.

All combinations of pairs within one set - deals with one set.

combinations between two lists? - doesn't allow repetition on 2nd set.

Finding all possible value combinations between two arrays - doesn't allow repetition on 2nd set.

An efficient method to generate all possible ways to pair up items in a data set - deals with single set, doesn't allow repetition.

I couldn't come up with a minimum example, as I don't know the algorithm.

Answer 1

In my solution, I make a counter – a vector with size of first list which stores iterators in second list. Then, everything becomes very easy (and even does not need much code for implementation.)

My sample code:

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

Output:

a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2

Live Demo on coliru

It's simply working like a trip meter where the first list provides number and labels of columns, and second list provides the values of columns: