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

Какая наиболее широко используемая существующая библиотека на C ++ дает всю комбинацию и перестановку k элементов из n элементов?

Я не прошу алгоритм, но существующую библиотеку или методы.

Благодарю.

Комбинации: из статьи Марка Нельсона по той же теме у нас есть next_combination http://marknelson.us/2002/03/01/next-permutation Перестановки: из STL у нас есть std :: next_permutation

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

Я решил протестировать решения дмэна и Чарльза Бейли здесь. Я назову их решениями A и B соответственно. Мой тест посещает каждую комбинацию vector size = 100, 5 за раз. Вот тестовый код:

Тестовый код

 struct F { unsigned long long count_; F() : count_(0) {} bool operator()(std::vector::iterator, std::vector::iterator) {++count_; return false;} }; int main() { typedef std::chrono::high_resolution_clock Clock; typedef std::chrono::duration sec; typedef std::chrono::duration ns; int n = 100; std::vector v(n); std::iota(v.begin(), v.end(), 0); std::vector::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 = " << rv.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, также содержит несколько других алгоритмов для enums и посещений перестановок с различными свойствами (круговыми, обратимыми и т. Д.). Каждый из этих алгоритмов был разработан с одной из целей. И обратите внимание, что ни один из этих алгоритмов не требует, чтобы начальная последовательность была в отсортированном порядке. Элементы не обязательно должны быть LessThanComparable .

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

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

 template 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 bool next_k_permutation(RandIt first, RandIt mid, RandIt last) { typedef typename std::iterator_traits::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 bool next_k_permutation(BiDiIt first, BiDiIt mid, BiDiIt last, Compare comp) { std::reverse(mid, last); return std::next_permutation(first, last, comp); } 

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

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

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

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

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

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

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

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

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

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

  • Отключить ошибки затмения (которые на самом деле не являются ошибками)
  • Преобразование строки в математическую оценку
  • C #: Что делать, если статический метод вызывается из нескольких streamов?
  • Чтение строки из ввода с символом пробела?
  • Использование MediaElement для воспроизведения видео из Stream
  • Ошибка связи C ++ после обновления до Mac OS X 10.9 / Xcode 5.0.1
  • WPF привязка данных к интерфейсу, а не к фактическому объекту - возможность литья?
  • С помощью Cream filestreams (fstream), как вы можете определить размер файла?
  • Несколько операций preincrement для переменной в C ++ (C?)
  • Уничтожение объектов в C ++
  • Портативный способ установки std :: thread priority в C ++ 11
  • Давайте будем гением компьютера.