views:

485

answers:

6

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?

A: 

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.
Potatoswatter
This seems right but not what I need.
bobber205
@bobber: can you be more specific?
Potatoswatter
+1  A: 

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)

AraK
Really really like this idea!
bobber205
Having trouble implementing this idea unfortunately.
bobber205
@bobber205 Could you explain what trouble you are facing?
AraK
Converting an integer to a bit array. I would have sworn I used to use a built in function for this before so I'm trying to write it myself. xD
bobber205
@bobber: the concept here is a powerset. It is different from what "combinations" typically refers to. Search for that instead. Also see http://stackoverflow.com/questions/2506119/combinations-algorithm .
Potatoswatter
@Potatoswatter Could you explain what you mean. Because the power set of a set, is the set of all possible combinations of set. I think you mean, there are better ways to produce combinations for a specified number of elements from the set.
AraK
@AraK: The powerset is the set of all possible *subsets* of a set. The usual definition of "combination" is http://en.wikipedia.org/wiki/Combination
Potatoswatter
@Potatoswatter Correct me if I am wrong please. A subset of a set is just a combination of that set with r elements out of n. Basically, the Power Set represents this: S is a set with n elements, then P(s) is: `C(n, 0) + C(n, 1) + C(n, 2) +...+ C(n, r) +...+ C(n, n)`
AraK
C(n,k) is the number of combinations. ∑[k=0..n](C(n,k)) = 2^n is a famous identity Pascal's Triangle. Maybe because function C takes argument k, some tend to assume the combinations question is predicated on a particular number of elements to be chosen.
Potatoswatter
A: 

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.

Greg Rogers
That doesn't appear to be a genuine Boost library…
Potatoswatter
No, but it works, and is licensed under the boost software license, so just stick the header file along with your source code...
Greg Rogers
A: 

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.

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n/131810#131810

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".

Maciej Hehl
A: 

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 
Potatoswatter
+3  A: 

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