From: ÐÛ½Ü³Â (benbearchen_at_[hidden])
Date: 2006-08-05 10:29:22
I wrote a Combination which is against to std::permutation.
It can enumerate all result of a combination, such as selecting 3
chars from "ABCDE", by `dictionary order'. It's just like the
The code is published at
http://www.bxmy.org/code/combination.cpp. And I wrote a article
about this Combination Algorithm in Chinese,
http://www.bxmy.org/article/combination.pdf. Also, the code can
be found in the enclosure.
The combination has at least three functions:
combination_adjust: should be called for initialize the sequence;
next_combination: get next combination, like next_permutation;
prev_combination: get previous combination, like prev_permutation.
This algorithm separates all elements into two parts. One is [first,
middle), the elements selected in. Other is [middle, last), the
elements selected out. The steps are:
1) find the first element `Pout' in [first, middle) which should be
2) find the first element `Qin' in [middle, last) which should be
3) iter_swap(Pout, Qin).
4) merge [Pout+1, middle) and [Qin+1, last).
It's simple and compatible with std::permutation well. I hope that
it can be add into the STL. They are couple.
Ben T. Bear
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk