Сочетание и перестановка в С++

Ответ 1

Комбинации: из статьи Марка Нельсона по той же теме у нас есть next_combination http://marknelson.us/2002/03/01/next-permutation Перестановки: из 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;
   }

Ответ 2

Я решил протестировать решения от dman и Charles Bailey. Я назову их решениями A и B соответственно. Мой тест посещает каждую комбинацию vector<int> size = 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 ГГц.

Решение A

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

Решение B

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

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

Решение C

Далее я попробовал решение из N2639, которое очень похоже на решение A, но работает правильно. Я назову это решение 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.

Ответ 3

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

Стандартная библиотека имеет 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

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

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

4 выберите 2 примера:
12 34
12 43 (после сортировки)
13 24 (после next_permutation)
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;
}