Getting Permutations with Repetitions in this special way

Question

I have a list of {a,b} and i need all possible combinatations where say n=3.

so: [a,b,a], [b,a,b] [a,a,a] [b,b,b]

etc.

Is there a name of such a problem

My current solution just uses random sampling and is very inefficient:

    void set_generator(const vector<int>& vec, int n){
        map<string, vector<int>> imap;
        int rcount = 0;
        while(1){
            string ms = "";
            vector<int> mset;
            for(int i=0; i<n; i++){
                int sampled_int = vec[rand() % vec.size()];
                ms += std::to_string(sampled_int);
                mset.emplace_back(sampled_int);
            }
            
            if(rcount > 100)
                break;
            if(imap.count(ms)){
                rcount += 1;
                //cout << "*" << endl;
                continue;
            }
            rcount = 0;
            imap[ms] = mset;
            cout << ms << endl;
            

        }
        
    }
    

        
    set_generator({1,2},3); 

Answer 1

Besides the concrete answer for integer usage, I want to provide a generic way I needed during test case construction for scenarios with a wide spread of various parameter variations. Maybe it's helpful to you too, at least for similar scenarios.

#include <vector>
#include <memory>

class SingleParameterToVaryBase
{
public:

  virtual bool varyNext() = 0;
  virtual void reset() = 0;
};

template <typename _DataType, typename _ParamVariationContType>
class SingleParameterToVary : public SingleParameterToVaryBase
{
public:

  SingleParameterToVary(
    _DataType& param,
    const _ParamVariationContType& valuesToVary) :
      mParameter(param)
    , mVariations(valuesToVary)
  {
    if (mVariations.empty())
      throw std::logic_error("Empty variation container for parameter");
    reset();
  }

  // Step to next parameter value, return false if end of value vector is reached
  virtual bool varyNext() override
  {
    ++mCurrentIt;

    const bool finished = mCurrentIt == mVariations.cend();

    if (finished)
    {
      return false;
    }
    else
    {
      mParameter = *mCurrentIt;
      return true;
    }
  }

  virtual void reset() override
  {
    mCurrentIt = mVariations.cbegin();
    mParameter = *mCurrentIt;
  }

private:

  typedef typename _ParamVariationContType::const_iterator ConstIteratorType;

  // Iterator to the actual values this parameter can yield
  ConstIteratorType mCurrentIt;

  _ParamVariationContType mVariations;

  // Reference to the parameter itself
  _DataType& mParameter;
};

class GenericParameterVariator
{
public:

  GenericParameterVariator() : mFinished(false)
  {
    reset();
  }

  template <typename _ParameterType, typename _ParameterVariationsType>
  void registerParameterToVary(
    _ParameterType& param,
    const _ParameterVariationsType& paramVariations)
  {
    mParametersToVary.push_back(
      std::make_unique<SingleParameterToVary<_ParameterType, _ParameterVariationsType>>(
        param, paramVariations));
  }

  const bool isFinished() const { return mFinished; }

  void reset()
  {
    mFinished = false;
    mNumTotalCombinationsVisited = 0;

    for (const auto& upParameter : mParametersToVary)
      upParameter->reset();
  }

  // Step into next state if possible
  bool createNextParameterPermutation()
  {
    if (mFinished || mParametersToVary.empty())
      return false;

    auto itPToVary = mParametersToVary.begin();
    while (itPToVary != mParametersToVary.end())
    {
      const auto& upParameter = *itPToVary;

      // If we are the very first configuration at all, do not vary.
      const bool variedSomething = mNumTotalCombinationsVisited == 0 ? true : upParameter->varyNext();
      ++mNumTotalCombinationsVisited;

      if (!variedSomething)
      {
        // If we were not able to vary the last parameter in our list, we are finished.
        if (std::next(itPToVary) == mParametersToVary.end())
        {
          mFinished = true;
          return false;
        }

        ++itPToVary;
        continue;
      }
      else
      {
        if (itPToVary != mParametersToVary.begin())
        {
          // Reset all parameters before this one
          auto itBackwd = itPToVary;
          do
          {
            --itBackwd;
            (*itBackwd)->reset();
          } while (itBackwd != mParametersToVary.begin());
        }

        return true;
      }
    }

    return true;
  }

private:

  // Linearized parameter set
  std::vector<std::unique_ptr<SingleParameterToVaryBase>> mParametersToVary;

  bool mFinished;
  size_t mNumTotalCombinationsVisited;

};

Possible usage:

GenericParameterVariator paramVariator;

  size_t param1;
  int param2;
  char param3;

  paramVariator.registerParameterToVary(param1, std::vector<size_t>{ 1, 2 });
  paramVariator.registerParameterToVary(param2, std::vector<int>{ -1, -2 });
  paramVariator.registerParameterToVary(param3, std::vector<char>{ 'a', 'b' });

  std::vector<std::tuple<size_t, int, char>> visitedCombinations;
  while (paramVariator.createNextParameterPermutation())
    visitedCombinations.push_back(std::make_tuple(param1, param2, param3));

Generates:

(1, -1, 'a')
(2, -1, 'a')
(1, -2, 'a')
(2, -2, 'a')
(1, -1, 'b')
(2, -1, 'b')
(1, -2, 'b')
(2, -2, 'b')

For sure, this can be further optimized/specialized. For instance you can simply add a hashing scheme and/or an avoid functor if you want to avoid effective repetitions. Also, since the parameters are held as references, one might consider to protect the generator from possible error-prone usage via deleting copy/assignement constructors and operators.

Time complexity is within the theoretical permutation complexity range.

Answer 2

Let us call b the size of the input vector.

The problem consists in generating all numbers from 0 to b^n - 1, in base b.

A simple solution increments the elements of an array one by one, each from 0 to b-1.

This is performed by the function increment in the code hereafter.

Output:

111
211
121
221
112
212
122
222

The code:

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

void set_generator_op (const std::vector<int>& vec, int n){
        std::map<std::string, std::vector<int>> imap;
        int rcount = 0;
        while(1){
            std::string ms = "";
            std::vector<int> mset;
            for(int i=0; i<n; i++){
                int sampled_int = vec[rand() % vec.size()];
                ms += std::to_string(sampled_int);
                mset.emplace_back(sampled_int);
            }
            
            if(rcount > 100)
                break;
            if(imap.count(ms)){
                rcount += 1;
                //cout << "*" << endl;
                continue;
            }
            rcount = 0;
            imap[ms] = mset;
            std::cout << ms << "\n";
        }
    }
    
// incrementation of a array of int, in base "base"
// return false if max is already attained
bool increment (std::vector<int>& cpt, int base) {
    int n = cpt.size();
    for (int i = 0; i < n; ++i) {
        cpt[i]++;
        if (cpt[i] != base) {
            return true;
        }
        cpt[i] = 0;
    }
    return false;
}

void set_generator_new (const std::vector<int>& vec, int n){
    int base = vec.size();
    std::vector<int> cpt (n, 0);
    
    while (true) {
        std::string permut = "";
        for (auto &k: cpt) {
            permut += std::to_string (vec[k]);
        }
        std::cout << permut << "\n";
        if (!increment(cpt, base)) return;
    }
}
    
int main() {   
    set_generator_op ({1,2},3); 
    std::cout << "\n";
    set_generator_new ({1,2},3); 
}

---

Following advices of Jarod42, I have

• suppressed the useless conversion to a string
• used a more elegant do ... while instead of the while true
• inversed the iterators for printing the result

Moreover, I have created a templated version of the program.

New output:

111
112
121
122
211
212
221
222

aaa
aab
aba
abb
baa
bab
bba
bbb

And the new code:

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


// incrementation of a array of int, in base "base"
// return false if max is already attained
bool increment (std::vector<int>& cpt, int base) {
    int n = cpt.size();
    for (int i = 0; i < n; ++i) {
        cpt[i]++;
        if (cpt[i] != base) {
            return true;
        }
        cpt[i] = 0;
    }
    return false;
}

template <typename T>
void set_generator_new (const std::vector<T>& vec, int n){
    int base = vec.size();
    std::vector<int> cpt (n, 0);
    do {
        for (auto it = cpt.rbegin(); it != cpt.rend(); ++it) {
            std::cout << vec[*it];
        }
        std::cout << "\n";
    } while (increment(cpt, base));
}
    
int main() {   
    set_generator_new<int> ({1,2}, 3); 
    std::cout << "\n";
    set_generator_new<char> ({'a','b'}, 3); 
}