Получение перестановок с повторениями этим особым способом

ProgramBox

Получение перестановок с повторениями этим особым способом

Post author:admin
Запись опубликована:16 февраля, 2023
Post category:Вопросы по программированию

#c #combinations

#c #комбинации

Вопрос:

У меня есть список {a, b}, и мне нужны все возможные комбинации, где, скажем, n = 3.

итак: [a, b,a], [b,a,b] [a,a,a] [b, b,b]

и т.д.

Есть ли название такой проблемы

Мое текущее решение просто использует случайную выборку и очень неэффективно:

     void set_generator(const vector<int>amp; 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);

Ответ №1:

Назовем b размером входного вектора.

Проблема заключается в генерации всех чисел от 0 до b ^ n — 1 в базе b.

Простое решение увеличивает элементы массива один за другим, каждый от 0 до b-1.

Это выполняется функцией increment в коде ниже.

Вывод:

Код:

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

void set_generator_op (const std::vector<int>amp; 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>amp; 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>amp; vec, int n){
    int base = vec.size();
    std::vector<int> cpt (n, 0);
    
    while (true) {
        std::string permut = "";
        for (auto amp;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); 
}

Следуя советам Jarod42, у меня есть

подавлено бесполезное преобразование в строку
используется более элегантный do ... while вместо while true
инвертировал итераторы для печати результата

Более того, я создал шаблонную версию программы.

Новый вывод:

 111
112
121
122
211
212
221
222

aaa
aab
aba
abb
baa
bab
bba
bbb

И новый код:

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

1. Мне это не кажется неэффективным. Какую идею вы имели в виду по поводу оптимизации?

2. @PatrickParker После дальнейших размышлений я понял, что среднее число итераций в increment ограничено b/(b-1) , что соответствует бесконечности n . Наихудший случай b=2 , и мы получаем в среднем 2 итерации путем генерации нового вектора. Так эффективно, на самом деле не неэффективно! Я удалил упоминание о неэффективности.

3. Я думаю, что проблема заключалась в комбинациях, поэтому 211, 121, 112 одинаковы, и только один должен быть напечатан или сгенерирован. Возможно, я ошибаюсь, просто мысль.

4. код @swag2198 OP генерирует 8 возможных комбинаций. Так что я думаю, это то, чего они хотят. Текст немного неоднозначен.

5. Я имел в виду это .

Ответ №2:

Помимо конкретного ответа на использование целых чисел, я хочу предоставить общий способ, который мне понадобился при построении тестового примера для сценариев с широким распространением различных вариаций параметров. Возможно, это тоже полезно для вас, по крайней мере, для подобных сценариев.

 #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(
    _DataTypeamp; param,
    const _ParamVariationContTypeamp; 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
  _DataTypeamp; mParameter;
};

class GenericParameterVariator
{
public:

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

  template <typename _ParameterType, typename _ParameterVariationsType>
  void registerParameterToVary(
    _ParameterTypeamp; param,
    const _ParameterVariationsTypeamp; 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 autoamp; 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 autoamp; 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;

};

Возможное использование:

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

Генерирует:

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

Конечно, это можно дополнительно оптимизировать / специализировать. Например, вы можете просто добавить схему хеширования и / или избегающий функтор, если хотите избежать эффективных повторений. Кроме того, поскольку параметры хранятся как ссылки, можно было бы рассмотреть возможность защиты генератора от возможного использования, связанного с ошибками, путем удаления конструкторов и операторов копирования / присвоения.

Временная сложность находится в пределах теоретического диапазона сложности перестановки.