комбинация и перестановка в C++
Какова существующая библиотека, которой наиболее широко пользуются, в C++ для предоставления всей комбинации и перестановки k элементов из n элементов?
Я не спрашиваю алгоритм, но существующую библиотеку или методы.
Спасибо.
2 ответа
Комбинации: из статьи Марка Нельсона по той же теме у нас есть 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;
}
Этот ответ обеспечивает решение с минимальными усилиями по реализации. Он может не обладать приемлемой производительностью, если вы хотите получить комбинации для больших диапазонов входных данных.
В стандартной библиотеке есть 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 является используемым сравнением.