Next_permutation for combinations or subsets in a parameter set

Question

Is there some equivalent library or function that will give me the following combination of a set of values, such as next_permutation, for me?

Answer 1

Combinations: from an article by Mark Nelson on the same topic, we have next_combination http://marknelson.us/2002/03/01/next-permutation
Permutations: from STL we have 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; } 

Answer 2

I do not know about that. The basic idea is to represent your elements as a bit array. So, for example, you have set S:

 S = {a, b, c} [i, j, k] // a is the first bit, b is the second bit, c is the third bit 

To generate a power set S (just generate all numbers ~ 3 bits in size with a simple addition):

 000 // {} 001 // {c} 010 // {b} 011 // {b, c} 100 // {a} 101 // {a, c} 110 // {a, b} 111 // {a, b, c} 

All you have to do is find which bits are set and associate them with your installed elements.

In conclusion, we note that there is one combination that you can create when you want all the elements to be used, and this combination was set up on its own, because the order does not matter in the combinations, so we are talking about several elements of n, where 0 <= n <= size(S)

Answer 3

I used this library when I needed it. It has an interface very similar to std::next_permutation , so it will be easy to use if you used it before.

Answer 4

Enumerating a power set (i.e., all combinations of all sizes) can use an adaptation of the binary increment algorithm.

 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.) } 

The bidirectional iterator requirement is unsuccessful and can be worked out.

I was going to get it to handle the same elements (multisets), but I need to go to bed: v (.

Using:

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

EDIT: Here is the multiset version. The set does not need to be sorted, but identical elements need to be grouped.

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

Output:

 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 

Answer 5

Googling for C++ "next_combination" this enabled.

• search from the "middle" back until you find an element that is less than * (end - 1). This is an element we must increase. Name it "Head_pos".
• look for the "end" back until you find the last element, which is still larger than * head_pos. Call it Tail_pos.
• swap head_pos and tail_pos. We reorder the elements from [head_pos + 1, mid [and [tail_pos + 1, end [when increasing the order.

Answer 6

In case you have no choice, but to implement your own function, perhaps this horror may help a little, or perhaps other horrors among the answers to this question.

Algorithm for returning all combinations of k elements from n

I wrote this a while ago, and the full picture is eluding me now :), but the main idea is this: You have the original combination, and the current combination is the iterator vector for the selected elements. To get the next combination, you scan your set from right to left, looking for a bubble. By “bubble” I mean one or more adjacent elements that are not selected. The "bubble" can be right on the right. Then, in your combination, you exchange the first element to the left of the “bubble” and all other elements from the combination that are on the right in the set, with the subset of adjacent elements that starts at the beginning of the “bubble”.