Есть ли некоторая эквивалентная библиотека или функция, которая даст мне, следующая комбинация множества значений как next_permutation в делает для меня?
Я не знаю ни одного. Основная идея - представить ваши элементы в виде битового массива. Так, например, у вас есть набор S:
S = {a, b, c}
[i, j, k] // a is the first bit, b is the second bit, c is the third bit
Чтобы сгенерировать набор степеней S (просто сгенерируйте все числа, которые имеют размер == 3 бита, с помощью простого сложения):
000 // {}
001 // {c}
010 // {b}
011 // {b, c}
100 // {a}
101 // {a, c}
110 // {a, b}
111 // {a, b, c}
Все, что вам нужно сделать, это чтобы узнать, какие биты установлены, и связать их с элементами вашего набора.
В заключение, есть одна комбинация, которую вы можете создать, когда хотите, чтобы использовались все элементы, и эта комбинация - это сам набор, потому что в комбинациях порядок не имеет значения, поэтому мы наверняка говорим о нескольких elements n где 0 <= n <= size (S)
В случае, если у Вас нет выбора, но для реализации Вашей собственной функции, возможно, этот ужас может немного помочь или, может быть, другие ужасы среди ответов на этот вопрос.
Алгоритм для возврата всех комбинаций k элементов из n
Я написал его некоторое время назад, и теперь полная картина ускользает от меня :), но основная идея такова: У вас есть исходный набор и Текущая комбинация - это вектор итераторов для выбранных элементов. Чтобы получить следующую комбинацию, вы просматриваете свой набор справа налево в поисках «пузыря». Под «пузырем» я подразумеваю один или несколько невыделенных соседних элементов. «Пузырь» может оказаться сразу справа. Затем в Вашей комбинации Вы обмениваете первый элемент слева от «пузыря» и все остальные элементы из комбинации, которые находятся справа в наборе, с подмножеством смежных элементов, которое начинается в начале « пузырь".
Я использовал эту библиотеку , когда мне нужно было это сделать. Он имеет интерфейс, очень похожий на std :: next_permutation
, поэтому его будет легко использовать, если вы уже использовали его раньше.
Перечисление набора мощности (то есть всех комбинаций всех размеров) может использовать адаптацию алгоритма двоичного приращения.
template< class I, class O > // I forward, O bidirectional iterator
O next_subset( I uni_first, I uni_last, // set universe in a range
O sub_first, O sub_last ) { // current subset in a range
std::pair< O, I > mis = std::mismatch( sub_first, sub_last, uni_first );
if ( mis.second == uni_last ) return sub_first; // finished cycle
O ret;
if ( mis.first == sub_first ) { // copy elements following mismatch
std::copy_backward( mis.first, sub_last, ++ (ret = sub_last) );
} else ret = std::copy( mis.first, sub_last, ++ O(sub_first) );
* sub_first = * mis.second; // add first element not yet in result
return ret; // return end of new subset. (Output range must accommodate.)
}
Требование двунаправленного итератора вызывает сожаление, и его можно обойти.
Я собирался заставить его обрабатывать идентичные элементы (мультимножества), но мне нужно лечь спать: v (.
Использование:
#include <iostream>
#include <vector>
using namespace std;
char const *fruits_a[] = { "apples", "beans", "cherries", "durian" };
vector< string > fruits( fruits_a, fruits_a + sizeof fruits_a/sizeof *fruits_a );
int main() {
vector< string > sub_fruits( fruits.size() );
vector< string >::iterator last_fruit = sub_fruits.begin();
while (
( last_fruit = next_subset( fruits.begin(), fruits.end(),
sub_fruits.begin(), last_fruit ) )
!= sub_fruits.begin() ) {
cerr << "size " << last_fruit - sub_fruits.begin() << ": ";
for ( vector<string>::iterator fit = sub_fruits.begin(); fit != last_fruit; ++ fit ) {
cerr << * fit << " ";
}
cerr << endl;
}
}
РЕДАКТИРОВАТЬ: Вот версия для мультимножеств. Набор не 'Не нужно сортировать, но идентичные элементы должны быть сгруппированы вместе.
#include <iterator>
#include <algorithm>
#include <functional>
template< class I, class O > // I forward, O bidirectional iterator
I next_subset( I uni_first, I uni_last, // set universe in a range
O sub_first, O sub_last ) { // current subset in a range
std::pair< O, I > mis = std::mismatch( sub_first, sub_last, uni_first );
if ( mis.second == uni_last ) return sub_first; // finished cycle
typedef std::reverse_iterator<O> RO;
mis.first = std::find_if( RO(mis.first), RO(sub_first), std::bind1st(
std::not_equal_to< typename std::iterator_traits<O>::value_type >(),
* mis.second ) ).base(); // move mis.first before identical grouping
O ret;
if ( mis.first != sub_first ) { // copy elements after mismatch
ret = std::copy( mis.first, sub_last, ++ O(sub_first) );
} else std::copy_backward( mis.first, sub_last, ++ (ret = sub_last) );
* sub_first = * mis.second; // add first element not yet in result
return ret;
}
#include <vector>
#include <iostream>
using namespace std;
char const *fruits_a[] = { "apples", "apples", "beans", "beans", "cherries" };
vector< string > fruits( fruits_a, fruits_a + sizeof fruits_a/sizeof *fruits_a );
int main() {
vector< string > sub_fruits( fruits.size() );
vector< string >::iterator last_fruit = sub_fruits.begin();
while (
( last_fruit = next_subset( fruits.begin(), fruits.end(),
sub_fruits.begin(), last_fruit )
) != sub_fruits.begin() ) {
cerr << "size " << last_fruit - sub_fruits.begin() << ": ";
for ( vector<string>::iterator fit = sub_fruits.begin(); fit != last_fruit; ++ fit ) {
cerr << * fit << " ";
}
cerr << endl;
}
}
Вывод:
size 1: apples
size 2: apples apples
size 1: beans
size 2: apples beans
size 3: apples apples beans
size 2: beans beans
size 3: apples beans beans
size 4: apples apples beans beans
size 1: cherries
size 2: apples cherries
size 3: apples apples cherries
size 2: beans cherries
size 3: apples beans cherries
size 4: apples apples beans cherries
size 3: beans beans cherries
size 4: apples beans beans cherries
size 5: apples apples beans beans cherries
Поиск в Google C ++ "next_combination"
обнаружил это .
- выполните поиск от "середины" назад, пока не найдете элемент, который меньше , чем * (конец - 1). Это элемент , который мы должны увеличивать. Назовите это "head_pos".
- выполните поиск от "end" назад, пока не найдете последний элемент, который все еще больше, чем * head_pos. Назовите это "tail_pos".
- поменять местами head_pos и tail_pos. Измените порядок элементов из [head_pos + 1, mid [ ] и [tail_pos + 1, end [в возрастающем порядке.
Комбинации: из статьи Марка Нельсона по той же теме у нас есть 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;
}