STL and combinations question

[Phil]

Thank you for reading my plea for help.

What I'm trying to achieve is to get the subsets from a given set using the
Standard Template Library.

Say, for example, I have created an empty set and then have inserted 3
numbers into that set (1, 2, 3). Next, I would like to get all of the subset
pairs (1, 2), (1, 3) and (2, 3) for processing.

A Google search has given me a lot to think about but nothing specific for
my needs. I have played with next_permutation and read about
next_combination which sounded more promising, since combinations are what
I'm looking for, but next_combination doesn't appear to be part of STL (572:
error: 'next_combination' was not declared in this scope).

Can someone please put me on the right track? Perhaps a simple example might
help.

 

[John Carson]

Thank you for reading my plea for help.

What I'm trying to achieve is to get the subsets from a given set
using the Standard Template Library.

Say, for example, I have created an empty set and then have inserted 3
numbers into that set (1, 2, 3). Next, I would like to get all of the
subset pairs (1, 2), (1, 3) and (2, 3) for processing.

A Google search has given me a lot to think about but nothing
specific for my needs. I have played with next_permutation and read
about next_combination which sounded more promising, since
combinations are what I'm looking for, but next_combination doesn't
appear to be part of STL (572: error: 'next_combination' was not
declared in this scope).
Can someone please put me on the right track? Perhaps a simple
example might help.

Algorithms for finding all subsets are not trivial and have nothing
specifically to do with the C++ language. Try

comp.programming

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Thank you for reading my plea for help.

What I'm trying to achieve is to get the subsets from a given set using the
Standard Template Library.

Say, for example, I have created an empty set and then have inserted 3
numbers into that set (1, 2, 3). Next, I would like to get all of the subset
pairs (1, 2), (1, 3) and (2, 3) for processing.

This can probably be done using any container but I find a vector
particularly useful in this case:

#include <vector>
#include <utils>

std::vector<int> set;
std::vector<std:air<int, int> > pairs;

// initialize the set somehow

for (size_t i = 0; i < set.size(); ++i)
for (size_t j = i + 1; j < set.size(); ++k)
pairs.push_back(std::make_pair(i, j));

This will run in about O((n^2) / 2).

 

[Gianni Mariani]

This can probably be done using any container but I find a vector
particularly useful in this case:

#include <vector>
#include <utils>

std::vector<int> set;
std::vector<std:air<int, int> > pairs;

// initialize the set somehow

for (size_t i = 0; i < set.size(); ++i)
for (size_t j = i + 1; j < set.size(); ++k)
pairs.push_back(std::make_pair(i, j));

This will run in about O((n^2) / 2).

Would boost's "next_combination" work ?

see this:
http://www.bxmy.org/code/combination.hpp

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Would boost's "next_combination" work ?

see this:
http://www.bxmy.org/code/combination.hpp

The link does not lead to code that is part of boost, and from the code
I saw it looked unnecessarily complicated, but it might work. Best way
to find out is to test it. You might also be interested in the
following: http://www.codeproject.com/cpp/CombC.asp

 

[Howard Hinnant]

Thank you for reading my plea for help.

What I'm trying to achieve is to get the subsets from a given set using the
Standard Template Library.

Say, for example, I have created an empty set and then have inserted 3
numbers into that set (1, 2, 3). Next, I would like to get all of the subset
pairs (1, 2), (1, 3) and (2, 3) for processing.

A Google search has given me a lot to think about but nothing specific for
my needs. I have played with next_permutation and read about
next_combination which sounded more promising, since combinations are what
I'm looking for, but next_combination doesn't appear to be part of STL (572:
error: 'next_combination' was not declared in this scope).

Can someone please put me on the right track? Perhaps a simple example might
help.

This question comes up often enough that I believe C++ should have a
standard solution. I do not find a need for this functionality often.
But I do need it sometimes. And when I need it, I really need it badly.
And it is very non-trivial to get right.

I most recently used the below-linked code to semi-automate the
generation of test cases for the rvalue reference work. I needed to
test all combinations of function calls involving lvalue and rvalue
arguments to overload sets containing const and/or volatile lvalue and
rvalue references (here's a link to those tests for the curious
http://home.twcny.rr.com/hinnant/cpp_extensions/rvalue_ref_test/).

Anyway, I've decided to make the fundamental combination (and
permutation) algorithms public. They can be found here, including a
couple of demoes:

http://home.twcny.rr.com/hinnant/cpp_extensions/combinations.html

The second demo (involving clusters of cities) is perhaps the most
interesting. It demonstrates the ability to perform a combination
calculation that itself involves computing over combinations.
Admittedly the demo could be coded more efficiently. But hasn't been
for the purpose of demonstrating this nested combination computation
capability.

This set of algorithms is not necessarily a complete set. But I do not
have the time to extend it for now. I currently have:

template<class BidirectionalIterator, class Function, class Size>
Function
for_each_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Size k, Function f);


template<class BidirectionalIterator, class Function, class Size>
Function
for_each_circular_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Size k, Function f);

template<class BidirectionalIterator, class Function, class Size>
Function
for_each_combination(BidirectionalIterator first,
BidirectionalIterator last,
Size k, Function f);

I wouldn't mind having "reversible permutation" versions. I.e. when you
consider a permutation and its reverse to be the same set, there's no
need to compute characteristics of both (e.g. if you're computing the
sum of distances between a sequence of locations, the distance is the
same whether the locations are traversed forwards or backwards). This
could cut the expense of the above permutation functions in half, but I
have not succeeded in coding those algorithms at this point.

Hth.

-Howard