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?

Longspur

you need to be much more specific – Sublingual

Probably even a little more specific will do. – Selfish

possible duplicate of #2212415 – Parlando

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

Gaona

I find it hard to trust that algorithm with its atrocious variable naming, obvious dead code etc. – Aldosterone

I'm still not sure about the correctness, but at least here's a lightly cleaner version paste.ubuntu.com/p/yXgtdjTyfD – Aldosterone

The lazy-web came back with this implementation which looks like it is much more heavy-duty. howardhinnant.github.io/combinations.html /cc @howard-hinnant – Aldosterone

The link is broekn. – Communicant

I have made an optimized version gist.github.com/viliml/eedbf77554ab7c748822c824289529fd – Masuria

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)

Vitrification

Really really like this idea! – Longspur

Having trouble implementing this idea unfortunately. – Longspur

@Longspur Could you explain what trouble you are facing? – Vitrification

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 – Longspur

@bobber: the concept here is a powerset. It is different from what "combinations" typically refers to. Search for that instead. Also see https://mcmap.net/q/1476011/-combinations-algorithm . – Parlando

@Parlando 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. – Vitrification

@AraK: The powerset is the set of all possible subsets of a set. The usual definition of "combination" is en.wikipedia.org/wiki/Combination – Parlando

@Parlando 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) – Vitrification

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. – Parlando

Answer 3

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 

Parlando

Answer 4

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.

Parlando

@bobber: can you be more specific? – Parlando

Answer 5

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.

Ladyinwaiting

That doesn't appear to be a genuine Boost library… – Parlando

No, but it works, and is licensed under the boost software license, so just stick the header file along with your source code... – Ladyinwaiting

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

Benzyl