Комбинация и перестановка в C++
Какая библиотека в С ++ наиболее широко используется для предоставления всей комбинации и перестановки k элементов из n элементов?
Я спрашиваю не об алгоритме, а о существующей библиотеке или методах.
Благодарю.
4 ответа
Комбинации: из статьи Марка Нельсона на ту же тему мы имеем следующую_комбинацию 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;
}
Я решил проверить решения Дмана и Чарльза Бейли здесь. Я назову их решениями А и Б соответственно. Мой тест посещает каждую комбинацию 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 ГГц.
Решение А
Решение A приводит к бесконечному циклу. Даже когда я делаю n очень маленькая, эта программа никогда не завершается. Впоследствии проголосовал по этой причине.
Решение Б
Это редактирование. Решение B изменилось в процессе написания этого ответа. Сначала он давал неправильные ответы, а из-за очень быстрого обновления теперь дает правильные ответы. Распечатывает:
N = 100, r = 5, visits = 75287520
next_combination total = 4519.84 seconds
next_combination per visit = 60034.3 ns
Решение С
Затем я попробовал решение из N2639, которое выглядит очень похоже на решение A, но работает правильно. Я назову это решение C, и оно распечатает:
N = 100, r = 5, visits = 75287520
next_combination total = 6.42602 seconds
next_combination per visit = 85.3531 ns
Раствор С в 703 раза быстрее, чем раствор В.
Решение 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 (после следующей_перестановки)
13 42 (после сортировки)
14 23 (после следующей_перестановки)
14 32 (после сортировки)
21 34 (после следующей_перестановки)
Поэтому я добавил проверку, чтобы убедиться, что значение курсивом в порядке, прежде чем вернуться, но определенно не подумал бы о той части, которую вы написали (очень элегантно! Спасибо!).
Не полностью проверено, только краткие тесты.
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')
Конечно, это может быть дополнительно оптимизировано / специализировано. Например, вы можете просто добавить схему хеширования и / или функтор избегания, если хотите избежать эффективных повторений. Кроме того, поскольку параметры хранятся как ссылки, можно подумать о защите генератора от возможного использования, подверженного ошибкам, путем удаления конструкторов и операторов копирования / присваивания.
Временная сложность находится в пределах теоретической сложности перестановки.