 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Phil
Guest
|
 Posted: Fri Dec 29, 2006 8:49 am Post subject: STL and combinations question |
 |
|
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.
--
Regards,
Phil. |
|
| Back to top |
|
 |
John Carson
Guest
|
| Posted: Fri Dec 29, 2006 10:10 am Post subject: Re: STL and combinations question |
|
|
"Phil" <phillor (AT) telstra (DOT) com> wrote in message
news:Tm%kh.15050$HU.989@news-server.bigpond.net.au
| Quote: | 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 |
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Tue Jan 02, 2007 8:10 am Post subject: Re: STL and combinations question |
|
|
In article <Tm%kh.15050$HU.989@news-server.bigpond.net.au>,
"Phil" <phillor (AT) telstra (DOT) com> wrote:
| Quote: | 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 |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
