From: Ð۽ܳ (benbearchen_at_[hidden])
Date: 2006-08-05 10:29:22
Hi!
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
std::permutation.
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
selected out.
2) find the first element `Qin' in [middle, last) which should be
selected in.
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.
Thanks.
Ben T. Bear