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:

Answer 2

These are permutations with repetition of the elements from B in disguise. If you are looking only at the elements from B (example from the OP) we have:

111
112
121
122
211
212
221
222

Which are precisely the permutations of B with repetition. The elements from A are simply filled in to obtain the desired result.

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

Calling it we have:

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

And here is the output:

Example 1 : 
a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2

Example 2 : 
a1b1
a1b2
a1b3
a2b1
a2b2
a2b3
a3b1
a3b2
a3b3

Here is a working example : https://ideone.com/OUv49P

Answer 3

Many possible solutions for this. Mine's building a string with a recursive call:

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

live example

Answer 4

Many solutions possible indeed, here is a my simple recursive solution, pretty similar to JHBonarious's but without the niceness of production code.

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