next_permutation for combinations or subsets in powerset

Question

Is there some equivalent library or function that will give me the next combination of a set of values like next_permutation in does for me?

Answer 1

Combinations: from Mark Nelson's article 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 am not aware of one. The basic idea is to represent your elements as a bit array. So for example, you have the 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 the Power Set of S(just generate all numbers that are of size == 3 bits by using the simple addition):

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

All what you have to do is to find what bits are set, and to relate them to your set's elements.

On final note, there is one combination you can produce when you want all elements to be used and that combination is the set it self, because in combinations the order doesn't matter so for sure we are talking about a number of elements n where 0 <= n <= size(S)

Answer 3

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

Answer 4

Enumeration of the powerset (that is, 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 requirement of a bidirectional iterator is unfortunate, and could be worked around.

I was going to make it handle identical elements (multisets), but I need to go to bed :v( .

Usage:

#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 version for multisets. The set doesn't have to be sorted but identical elements do have to be grouped together.

#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" turned up this.

• search from "mid" backwards until you find an element that is smaller than *(end - 1). This is the element we should increment. Call this "head_pos".
• search from "end" backwards until you find the last element that is still larger than *head_pos. Call it "tail_pos".
• swap head_pos and tail_pos. Re-order the elements from [head_pos + 1, mid[ and [tail_pos + 1, end[ in increasing order.

Answer 6

In case You have no choice, but to implement Your own function maybe this horror can help a bit or maybe other horrors among answers to that question.

Algorithm to return all combinations of k elements from n

I wrote it some time ago and the full picture eludes me now :), but the basic idea is this: You have the original set and current combination is a vector of iterators to the elements selected. 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 not selected. The "bubble" might be immediately at the right. Then, in Your combination, You exchange the first element at the left of the "bubble" and all other elements from the combination, that are to the right in the set, with a subset of adjacent elements that starts at the beginning of the "bubble".