# STL and combinations question

Discussion in 'C++' started by Phil, Dec 29, 2006.

1. ### PhilGuest

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

--
Regards,
Phil.

Phil, Dec 29, 2006

2. ### John CarsonGuest

"Phil" <> wrote in message
news:Tm%kh.15050\$
> 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

--
John Carson

John Carson, Dec 29, 2006

3. ### =?ISO-8859-1?Q?Erik_Wikstr=F6m?=Guest

On 2006-12-29 03:49, Phil wrote:
> 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).

--
Erik Wikström

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Dec 30, 2006
4. ### Gianni MarianiGuest

Erik Wikström wrote:
> On 2006-12-29 03:49, Phil wrote:
>> 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).

Would boost's "next_combination" work ?

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

Gianni Mariani, Dec 30, 2006
5. ### =?ISO-8859-1?Q?Erik_Wikstr=F6m?=Guest

On 2006-12-30 23:06, Gianni Mariani wrote:
> Erik Wikström wrote:
>> On 2006-12-29 03:49, Phil wrote:
>>> 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).

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

--
Erik Wikström

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Dec 31, 2006
6. ### Howard HinnantGuest

In article <Tm%kh.15050\$>,
"Phil" <> wrote:

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

Howard Hinnant, Jan 2, 2007