STL combination
Jack Applin
generate all possible 5-card hands from a 52-card deck.
I was surprised that there doesn't seem to be a next_combination,
akin to next_permutation.
--
Jack Applin
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Juergen Heinzl
>I'm looking for a way to do combinations in STL. For example, I want to
>generate all possible 5-card hands from a 52-card deck.
>
>I was surprised that there doesn't seem to be a next_combination,
>akin to next_permutation.
I guess it is easy enough to extend it, so here is a code snippet ...
void combinations( unsigned sov, unsigned eov, unsigned m, char* cvec ) {
for( unsigned i = sov; (i + m - 1) < eov; i++ ) {
for( unsigned j = i + 1; (j + m - 1) <= eov; j++ ) {
std::cout << cvec[i];
for( unsigned k = 1; k < m; k++ ) {
std::cout << cvec[j + k - 1];
}
std::cout << std::endl;
}
}
}
... that prints out all m combinations of a char vector 0 ... N. It
was only meant as a how-to to for a more elaborate programme to
automate some testing.
Try ...
char cv[26] = { 'a','b', ... 'z' };
combinations( 0, 26, 5, cv );
...
Ta',
Juergen
--
\ Real name : Jürgen Heinzl \ no flames /
\ EMail Private : jue...@monocerus.demon.co.uk \ send money instead /
John Potter
Heinzl) wrote:
: In article <81t550$mvq$1...@fcnews.fc.hp.com>, Jack Applin wrote:
: >I'm looking for a way to do combinations in STL. For example, I want to
: >generate all possible 5-card hands from a 52-card deck.
: >
: >I was surprised that there doesn't seem to be a next_combination,
: >akin to next_permutation.
:
: I guess it is easy enough to extend it, so here is a code snippet ...
<Incorrect code snipped>
: ... that prints out all m combinations of a char vector 0 ... N. It
: was only meant as a how-to to for a more elaborate programme to
: automate some testing.
:
: Try ...
: char cv[26] = { 'a','b', ... 'z' };
: combinations( 0, 26, 5, cv );
char cv[] = "abcde";
combinations(0, 5, 3, cv);
Gives:
abc
abd
abe
bcd
bde
cde
Missing:
acd
ace
ade
bce
Back to the drawing board :)
John
John E. Potter
On 29 Nov 1999, Jack Applin wrote:
> I'm looking for a way to do combinations in STL. For example, I want to
> generate all possible 5-card hands from a 52-card deck.
>
> I was surprised that there doesn't seem to be a next_combination,
> akin to next_permutation.
Humm. An algorithm? How about nailing down the interface first?
Usage:
Container universe;
// fill it in with the set (bag?)
int comboSize;
// give it a value
Container::iterator it(universe.begin());
advance(it, comboSize);
Container combo;
copy(universe.begin(), it, someInserter(combo));
do
use(combo);
while (next_combination(combo.begin(), combo.end(), universe.begin(),
universe.end());
Sample:
string universe("abcdefghijklm");
string combo(universe.substr(0, 5));
do
cout << combo << endl;
while (next_combination(combo.begin(), combo.end(), universe.begin(),
universe.end());
Is that what you had in mind? What about duplicates in the universe?
Given "abbcc" what are the combinations of size 3?
abB abc abC aBc aBC acC bBc bBC bcC BcC
or just
abb abc acc bbc bcc
or just
abc
or it is the users problem and you don't care?
Jack Applin
> I'm looking for a way to do combinations in STL.
Juergen Heinzl wrote:
> I guess it is easy enough to extend it, so here is a code snippet ...
I'm afraid that we must have different definitions of "combinations".
Your code prints 253 groups of 5 letters, and I'm expecting a lot more.
For example, "aeiou" isn't present.
--
Jack Applin
Christopher Eltschka
>
> On 29 Nov 1999, Jack Applin wrote:
>
> > I'm looking for a way to do combinations in STL. For example, I want to
> > generate all possible 5-card hands from a 52-card deck.
> >
> > I was surprised that there doesn't seem to be a next_combination,
> > akin to next_permutation.
>
> Humm. An algorithm? How about nailing down the interface first?
>
> Usage:
>
> Container universe;
> // fill it in with the set (bag?)
> int comboSize;
> // give it a value
> Container::iterator it(universe.begin());
> advance(it, comboSize);
> Container combo;
> copy(universe.begin(), it, someInserter(combo));
> do
> use(combo);
> while (next_combination(combo.begin(), combo.end(), universe.begin(),
> universe.end());
There could also be a simpler interface, which just uses the
first n elements of the "universe" as n-card hand:
#include <iterator>
#include <algorithm>
#include <functional>
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator end,
BidirectionalIterator hand_end);
template<class BidirectionalIterator, class Compare>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator end,
BidirectionalIterator hand_end,
Compare comp);
// interprets the first n elements of the sequence as "hand"
// and the rest as "size"; gives the next combination for the
// "hand". To avoid permutations of the same hand to be generated,
// Iterator::value_type must be less-than-comparable for the
// three-argument-version
//
// Preconditions:
// - [begin, end) must be a valid range
// - [begin, hand_end) must be a valid subrange of [begin, end)
// - The sequences [begin, hand_end) and [hand_end, end) must
// be sorted
// - begin, end and hand_and must be mutable iterators
//
// return value:
// true, if the sequence is now sorted (if starting with a sorted
// sequence, this means that all hands were generated)
// false otherwise
//
// After return from next_combination, [begin, hand_end) and
// [hand_end, end) are sorted again.
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator end,
BidirectionalIterator hand_end)
{
return next_combination(
begin, end, hand_end,
std::less<typename
iterator_traits<BidirectionalIterator>::value_type>());
}
template<class BidirectionalIterator, class Compare>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator end,
BidirectionalIterator hand_end,
Compare comp)
{
if (hand_end == begin)
return true;
BidirectionalIterator hand = hand_end;
BidirectionalIterator deck;
do
{
--hand;
deck = std::upper_bound(hand_end, end, *hand, comp);
} while (hand !=begin && deck == end);
if (deck == end)
{
std::rotate(begin, hand_end, end);
return true;
}
BidirectionalIterator hand_next = hand;
++hand_next;
std::rotate(hand_next, deck, end);
std::rotate(hand, hand_next, end);
std::sort(hand_end, end); // should be improved ;-)
return false;
}
// Usage example
#include <iostream>
#include <string>
int main()
{
std::string deck;
int count;
std::cin >> deck >> count;
bool ready;
do
{
std::cout << deck.substr(0, count) << " "
<< deck.substr(count) << std::endl;
ready = next_combination(deck.begin(),
deck.end(),
deck.begin()+count);
} while(!ready);
cout << deck << endl;
}
I'm sure with some careful investigation of the effect of the
two rotations, the sort could be replaced by some rotations/swaps
as well.
[...]
> Is that what you had in mind? What about duplicates in the universe?
> Given "abbcc" what are the combinations of size 3?
> abB abc abC aBc aBC acC bBc bBC bcC BcC
> or just
> abb abc acc bbc bcc
> or just
> abc
> or it is the users problem and you don't care?
My code above gives just abb abc acc bbc bcc
Juergen Heinzl
>Jack Applin wrote:
>> I'm looking for a way to do combinations in STL.
>
>> I guess it is easy enough to extend it, so here is a code snippet ...
>
>I'm afraid that we must have different definitions of "combinations".
>Your code prints 253 groups of 5 letters, and I'm expecting a lot more.
>For example, "aeiou" isn't present.
I am afraid no, the algorithm is wrong ... late night hacking. Simple
enough to check, as the # of combinations n of a set k is ...
n!
--------
k!(n-k)!
... which does exclude removing duplicate elements BTW, say even a
set {a,a,a,a,a} should result in 10 combinations of 3 IMHO.
I know where the corner is,
Juergen
--
\ Real name : Jürgen Heinzl \ no flames /
\ EMail Private : jue...@monocerus.demon.co.uk \ send money instead /
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
John Potter
<celt...@physik.tu-muenchen.de> wrote:
: "John E. Potter" wrote:
: >
: > On 29 Nov 1999, Jack Applin wrote:
: >
: > > I'm looking for a way to do combinations in STL. For example, I want to
: > > generate all possible 5-card hands from a 52-card deck.
: > >
: > > I was surprised that there doesn't seem to be a next_combination,
: > > akin to next_permutation.
: >
: > Humm. An algorithm? How about nailing down the interface first?
: >
: > Usage:
: >
: > Container universe;
: > // fill it in with the set (bag?)
: > int comboSize;
: > // give it a value
: > Container::iterator it(universe.begin());
: > advance(it, comboSize);
: > Container combo;
: > copy(universe.begin(), it, someInserter(combo));
: > do
: > use(combo);
: > while (next_combination(combo.begin(), combo.end(), universe.begin(),
: > universe.end());
:
: There could also be a simpler interface, which just uses the
: first n elements of the "universe" as n-card hand:
Yes, I like that. I have an implementation of the four iterator
version which runs in about a third of the time for your version.
: I'm sure with some careful investigation of the effect of the
: two rotations, the sort could be replaced by some rotations/swaps
: as well.
Sure can. Please excuse me for changing the parameter order to
first, mid, last and the return to false when in raps back to
the beginning. These agree with the usage in rotate and
next_permutation. Here is the simple version assuming operator<.
Not as nicely formalized as yours, but runs slightly faster than
my original.
John
#include <algorithm>
template <class BI>
bool next_combination (BI first, BI mid, BI last) {
BI x(last);
-- x;
bool found(mid != last &&
(x = std::upper_bound(first, mid, *x)) != first);
if (found) {
BI b1(x --);
BI m1(std::upper_bound(mid, last, *x));
BI y(m1 ++);
std::swap(*x, *y);
if (b1 != mid && m1 != last) {
BI e1(m1);
BI m2(mid);
for (BI z = b1; z != mid && e1 != last; ++ z, ++ e1)
++ m2;
std::rotate(b1, m1, e1);
std::rotate(mid, m2, last);
}
}
else
std::rotate(first, mid, last);
return found;
Christopher Eltschka
[...]
However, it fails in the "three of abbcc" case. Haven't analyzed why.
Here's an improved version of my code.
The modifications are:
- replaced std::sort with a rotation
- replaced the loop with three sequencial calls of upper_bound/
lower_bound, with early handling of the case of replacing the
last element of the hand (I've seen that you don't have such
a loop, so I thought, if you can it, I can, too :-))
- modified the interface the same as you did
#include <iterator>
#include <algorithm>
#include <functional>
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator end,
BidirectionalIterator hand_end);
template<class BidirectionalIterator, class Compare>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator end,
BidirectionalIterator hand_end,
Compare comp);
// interprets the first elements of the sequence (between begin and
// hand_end) as "hand" and the rest as "size"; gives the next
// combination for the "hand". To avoid permutations of the same
// hand to be generated, Iterator::value_type must be
// less-than-comparable for the three-argument-version
//
// Preconditions:
// - [begin, end) must be a valid range
// - [begin, hand_end) must be a valid subrange of [begin, end)
// - The sequences [begin, hand_end) and [hand_end, end) must
// be sorted
// - begin, end and hand_and must be mutable iterators
// - updated comment
//
// return value:
// false, if the sequence is now sorted (if starting with a sorted
// sequence, this means that all hands were generated)
// true otherwise
//
// After return from next_combination, [begin, hand_end) and
// [hand_end, end) are sorted again.
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator hand_end,
BidirectionalIterator end)
{
return next_combination(
begin, hand_end, end,
std::less<typename
iterator_traits<BidirectionalIterator>::value_type>());
}
template<class BidirectionalIterator, class Compare>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator hand_end,
BidirectionalIterator end,
Compare comp)
{
if (hand_end == begin)
return false;
BidirectionalIterator hand = hand_end;
BidirectionalIterator deck;
do
{
--hand;
deck = std::upper_bound(hand_end, end, *hand, comp);
} while (hand !=begin && deck == end);
if (deck == end)
{
std::rotate(begin, hand_end, end);
return false;
}
BidirectionalIterator hand_next = hand;
++hand_next;
BidirectionalIterator sort_pos = end;
std::advance(sort_pos, -distance(hand_end, deck)-1);
std::rotate(hand_next, deck, end);
std::rotate(hand, hand_next, end);
std::rotate(hand_end, sort_pos, end);
return true;
}
// Usage example
#include <iostream>
#include <string>
int main()
{
std::string deck;
int count;
std::cin >> deck >> count;
bool ready;
do
{
std::cout << deck.substr(0, count) << " "
<< deck.substr(count) << std::endl;
ready = !next_combination(deck.begin(),
deck.begin()+count,
deck.end());
} while(!ready);
cout << deck << endl;
}
Since now there's no loop left, the worst case complexity is
linear in end-begin (the rotation going to the sorted case!).
Maybe there's still room for improvement in the three-rotation
sequence at the end.
John Potter
<celt...@physik.tu-muenchen.de> wrote:
: However, it fails in the "three of abbcc" case. Haven't analyzed why.
Yep.
// Requires [first, last) is a set. ;-)
Alright, it's cheap; so let's fix it.
Replace the first upper_bound with lower_bound.
: Here's an improved version of my code.
: - replaced the loop with three sequencial calls of upper_bound/
: lower_bound, with early handling of the case of replacing the
: last element of the hand (I've seen that you don't have such
: a loop, so I thought, if you can it, I can, too :-))
I don't see that in your code.
: BidirectionalIterator hand = hand_end;
: BidirectionalIterator deck;
:
: do
: {
: --hand;
: deck = std::upper_bound(hand_end, end, *hand, comp);
: } while (hand !=begin && deck == end);
I replaced that code with my lower_bound and my upper_bound after the
following if statement. That made it slightly slower/faster.
: std::rotate(hand_next, deck, end);
: std::rotate(hand, hand_next, end);
: std::rotate(hand_end, sort_pos, end);
:
: Maybe there's still room for improvement in the three-rotation
: sequence at the end.
Yes, that seems to be the major difference.
I played around a bit with my version and found that the test for the
special cases where there would be no rotation made no difference. I
also tried replacing the for loop with a min of two distances and
two advances. That slowed things down. Using a compare object made
no change.
The requirements for my original four iterator were that the type be
equality comparible, the combination be a subset of the universe, and
that any duplicates in the universe be adjacent. It returns false
when the combination becomes the leading subset of the universe. The
combinations are ordered by the collating sequence formed by the
universe.
With a driver that simply counts the number of permutations the time
for 52 choose 5 and 52 choose 47, using my original on 52 5 as 1.
John original(4) 1 3
John final 5 4
Chris (my no loop) 34 12
Chris as posted 33 17
Chris original 87 20
Here is my final (I think) version.
John
#include <algorithm>
template <class BI>
bool next_combination (BI first, BI mid, BI last) {
BI b1(last);
bool found(mid != last &&
(b1 = std::lower_bound(first, mid, *--b1)) != first);
if (! found)
std::rotate(first, mid, last);
else {
BI m1(std::upper_bound(mid, last, *--b1));
std::swap(*b1, *m1);
BI e1(++m1);
BI m2(mid);
for (BI z = ++b1; z != mid && e1 != last; ++ z, ++ e1)
++ m2;
std::rotate(b1, m1, e1);
std::rotate(mid, m2, last);
}
return found;
Christopher Eltschka
>
> On 6 Dec 1999 14:21:13 -0500, Christopher Eltschka
> <celt...@physik.tu-muenchen.de> wrote:
>
> : However, it fails in the "three of abbcc" case. Haven't analyzed why.
>
> Yep.
> // Requires [first, last) is a set. ;-)
> Alright, it's cheap; so let's fix it.
> Replace the first upper_bound with lower_bound.
>
>
> : - replaced the loop with three sequencial calls of upper_bound/
> : lower_bound, with early handling of the case of replacing the
> : last element of the hand (I've seen that you don't have such
> : a loop, so I thought, if you can it, I can, too :-))
>
Oops, the dangers of copy&paste - I've copied the wrong version :-(
Here's the version I intended to paste here:
// return value:
// false, if the sequence is now sorted (if starting with a sorted
// sequence, this means that all hands were generated)
// true otherwise
//
// After return from next_combination, [begin, hand_end) and
// [hand_end, end) are sorted again.
template<class BidirectionalIterator>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator hand_end,
BidirectionalIterator end)
{
return next_combination(
begin, hand_end, end,
std::less<typename
iterator_traits<BidirectionalIterator>::value_type>());
}
template<class BidirectionalIterator, class Compare>
bool next_combination(BidirectionalIterator begin,
BidirectionalIterator hand_end,
BidirectionalIterator end,
Compare comp)
{
if (hand_end == begin)
return false;
BidirectionalIterator hand = hand_end;
BidirectionalIterator deck;
// do
// {
// --hand;
// deck = std::upper_bound(hand_end, end, *hand, comp);
// } while (hand !=begin && deck == end);
// if (deck == end)
// {
// std::rotate(begin, hand_end, end);
// return false;
// }
--hand;
deck = std::upper_bound(hand_end, end, *hand, comp);
if (deck != end)
{
std::swap(*hand, *deck);
return true;
}
--deck;
hand = std::lower_bound(begin, hand_end, *deck, comp);
if (hand == begin)
{
std::rotate(begin, hand_end, end);
return false;
}
BidirectionalIterator hand_next = hand;
--hand;
deck = std::upper_bound(hand_end, end, *hand, comp);
BidirectionalIterator sort_pos = end;
std::advance(sort_pos, -distance(hand_end, deck)-1);
std::rotate(hand_next, deck, end);
std::rotate(hand, hand_next, end);
std::rotate(hand_end, sort_pos, end);
return true;
}
// Usage example
#include <iostream>
#include <string>
int main()
{
std::string deck;
int count;
std::cin >> deck >> count;
bool ready;
do
{
std::cout << deck.substr(0, count) << " "
<< deck.substr(count) << std::endl;
ready = !next_combination(deck.begin(),
deck.begin()+count,
deck.end());
} while(!ready);
cout << deck << endl;
}
>
> : BidirectionalIterator hand = hand_end;
> : BidirectionalIterator deck;
> :
> : do
> : {
> : --hand;
> : deck = std::upper_bound(hand_end, end, *hand, comp);
> : } while (hand !=begin && deck == end);
>
> I replaced that code with my lower_bound and my upper_bound after the
> following if statement. That made it slightly slower/faster.
>
> : std::rotate(hand_next, deck, end);
> : std::rotate(hand, hand_next, end);
> : std::rotate(hand_end, sort_pos, end);
> :
> : Maybe there's still room for improvement in the three-rotation
> : sequence at the end.
>
Interesting: Une upper_bound and one rotation less than my version.
OTOH, my current code has two early cases, especially I'm not
treating the (probably most common) case of the last element of the
hand to be replaced as first early return, with just a single
swap in this case. Given that for hands of length k out of n
different elements the number of hands is n!/(k!(n-k)!),
while the number of hands which end with the largest element
is (n-1)!/((k-1)!(n-k)!), we get that only in k/n of the
cases the complete algorithm is running; in the rest there's
just one upper_bound and one swap. (This also suggests that
it could be worthwhile to use a modified algorithm for
random-access-iterators, which determines the smaller of the
two partial sequences: If the left is one hand,. the right is,
too, but in lexicographical _de_creasing order; that is, a
next_combination on the first hand is eqvivalent to a
prev_combination on the second hand.)
OTOH your algorithm should be more efficient in the "run
through" case, since you're using two rotations instead of
three for the final permutation.
I now recognice that the first determined value of deck is
used for two things: First, to see if it is end, and only if
not, to determine the position for swap. Since it's easy to
determine if the result will be end by simply comparing with
*(end-1), that should go into the condition, and only after
determining that *(end-1) < *(hand-1), upper_bound is needed
to determine the swap position. This removes one upper_bound
from the special path (resulting in the equivalent to your
"*_bound-sequence" in that case).