Библиотечная функция для перестановки и комбинации в C++

Комбинации: из статьи Марка Нельсона на ту же тему, что и у нас. next_combination Перестановки: из STL у нас есть std::next_permutation

   template <typename Iterator>
   inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
   {
      if ((first == last) || (first == k) || (last == k))
         return false;
      Iterator itr1 = first;
      Iterator itr2 = last;
      ++itr1;
      if (last == itr1)
         return false;
      itr1 = last;
      --itr1;
      itr1 = k;
      --itr2;
      while (first != itr1)
      {
         if (*--itr1 < *itr2)
         {
            Iterator j = k;
            while (!(*itr1 < *j)) ++j;
            std::iter_swap(itr1,j);
            ++itr1;
            ++j;
            itr2 = k;
            std::rotate(itr1,j,last);
            while (last != j)
            {
               ++j;
               ++itr2;
            }
            std::rotate(k,itr2,last);
            return true;
         }
      }
      std::rotate(first,k,last);
      return false;
   }

Я решил протестировать решения dman и Charles Bailey здесь. Я буду называть их растворами A и B соответственно. Мой тест заключается в посещении каждой комбинации размера vector<int> = 100, по 5 за раз. Вот тестовый код:

Проверочный код

struct F
{
    unsigned long long count_;

    F() : count_(0) {}

    bool operator()(std::vector<int>::iterator, std::vector<int>::iterator)
    {++count_; return false;}
};

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    typedef std::chrono::duration<double, std::nano> ns;
    int n = 100;
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 0);
    std::vector<int>::iterator r = v.begin() + 5;
    F f;
    Clock::time_point t0 = Clock::now();
    do
    {
        f(v.begin(), r);
    } while (next_combination(v.begin(), r, v.end()));
    Clock::time_point t1 = Clock::now();
    sec s0 = t1 - t0;
    ns pvt0 = s0 / f.count_;
    std::cout << "N = " << v.size() << ", r = " << r-v.begin()
              << ", visits = " << f.count_ << '\n'
              << "\tnext_combination total = " << s0.count() << " seconds\n"
              << "\tnext_combination per visit = " << pvt0.count() << " ns";
}

Весь код был скомпилирован с помощью clang++ -O3 на процессоре Intel Core i5 с тактовой частотой 2,8 ГГц.

Решение А

Решение А приводит к бесконечному циклу. Даже когда я делаю n очень маленьким, эта программа никогда не завершается. Впоследствии по этой причине проголосовали против.

Решение Б

Это редактирование. Решение B изменилось в ходе написания этого ответа. Сначала он давал неверные ответы, а благодаря очень быстрому обновлению теперь дает правильные ответы. Он распечатывает:

N = 100, r = 5, visits = 75287520
    next_combination total = 4519.84 seconds
    next_combination per visit = 60034.3 ns

Решение В

Затем я попробовал решение из N2639. который очень похож на решение А, но работает правильно. Я назову это решение C, и оно распечатает:

N = 100, r = 5, visits = 75287520
    next_combination total = 6.42602 seconds
    next_combination per visit = 85.3531 ns

Решение C в 703 раза быстрее, чем решение B.

Решение D

Наконец, есть решение D, найденное здесь. Это решение имеет другую подпись/стиль и называется for_each_combination и используется так же, как std::for_each. Приведенный выше код драйвера изменяется между вызовами таймера следующим образом:

Clock::time_point t0 = Clock::now();
f = for_each_combination(v.begin(), r, v.end(), f);
Clock::time_point t1 = Clock::now();

Решение D распечатывает:

N = 100, r = 5, visits = 75287520
    for_each_combination = 0.498979 seconds
    for_each_combination per visit = 6.62765 ns

Решение D в 12,9 раза быстрее, чем решение C, и более чем в 9000 раз быстрее, чем решение B.

Я считаю это относительно небольшой проблемой: всего 75 миллионов посещений. По мере того, как количество посещений увеличивается до миллиардов, расхождение в производительности между этими алгоритмами продолжает расти. Решение B уже громоздко. Решение C в конечном итоге становится громоздким. Решение D — самый эффективный алгоритм для посещения всех известных мне комбинаций.

ссылка, показывающая решение D, также содержит несколько других алгоритмов для перечисления и посещения перестановок с различными свойствами (круговые, обратимый и др.). Каждый из этих алгоритмов был разработан с учетом производительности в качестве одной из целей. Обратите внимание, что ни один из этих алгоритмов не требует, чтобы исходная последовательность была отсортирована. Элементов даже не должно быть LessThanComparable.

Этот ответ обеспечивает решение с минимальными усилиями по реализации. Он может иметь неприемлемую производительность, если вы хотите получить комбинации для больших входных диапазонов.

В стандартной библиотеке есть std::next_permutation, и вы можете тривиально построить из него next_k_permutation и next_combination.

template<class RandIt, class Compare>
bool next_k_permutation(RandIt first, RandIt mid, RandIt last, Compare comp)
{
    std::sort(mid, last, std::tr1::bind(comp, std::tr1::placeholders::_2
                                            , std::tr1::placeholders::_1));
    return std::next_permutation(first, last, comp);
}

Если у вас нет tr1::bind или boost::bind, вам нужно будет создать объект функции, который меняет аргументы на заданное сравнение. Конечно, если вас интересует только std::less вариант next_combination, вы можете использовать std::greater напрямую:

template<class RandIt>
bool next_k_permutation(RandIt first, RandIt mid, RandIt last)
{
    typedef typename std::iterator_traits<RandIt>::value_type value_type;

    std::sort(mid, last, std::greater< value_type >());
    return std::next_permutation(first, last);
}

Это относительно безопасная версия next_combination. Если вы можете гарантировать, что диапазон [mid, last) находится в том же порядке, что и после вызова next_combination, вы можете использовать более простой вариант:

template<class BiDiIt, class Compare>
bool next_k_permutation(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp)
{
    std::reverse(mid, last);
    return std::next_permutation(first, last, comp);
}

Это также работает с двунаправленными итераторами, а также с итераторами произвольного доступа.

Чтобы вывести комбинации вместо k-перестановок, мы должны убедиться, что выводим каждую комбинацию только один раз, поэтому мы вернем комбинацию только в том случае, если это k-перестановка по порядку.

template<class BiDiIt, class Compare>
bool next_combination(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp)
{
    bool result;
    do
    {
        result = next_k_permutation(first, mid, last, comp);
    } while (std::adjacent_find( first, mid,
                             std::tr1::bind(comp, std::tr1::placeholders::_2
                                                , std::tr1::placeholders::_1) )
                                                                        != mid );
    return result;
}

В качестве альтернативы можно было бы использовать обратный итератор вместо вызова bind для замены параметров или явно использовать std::greater, если используется сравнение std::less.

@ Чарльз Бейли выше:

Я могу ошибаться, но я думаю, что первые два алгоритма выше не удаляют дубликаты между первым и средним? Может быть, я не уверен, как его использовать.

4 выберите 2 пример:
12 34
12 43 (после сортировки)
13 24 (после next_permutation)< br> 13 42 (после сортировки)
14 23 (после next_permutation)
14 32 (после сортировки)
21 34 (после next_permutation)

Поэтому я добавил проверку, чтобы убедиться, что значение, выделенное курсивом, в порядке перед возвратом, но определенно не подумал бы о той части, которую вы написали (очень элегантно! спасибо!).

Не полностью проверено, только беглые тесты ..

template
bool next_combination(RandIt first, RandIt mid, RandIt last)
{
    typedef typename std::iterator_traits< RandIt >::value_type value_type;
    std::sort(mid, last, std::greater< value_type >() );
    while(std::next_permutation(first, last)){
        if(std::adjacent_find(first, mid, std::greater< value_type >() ) == mid){
            return true;
        }
        std::sort(mid, last, std::greater< value_type >() );
    return false;
}

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

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

};

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

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

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

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