some mistake or changes about partial permutation in section "Descriptions". next_partial_permutation: Effects: ... If such a subsequence does not exist, "it sorts the entire range". ---- Change to ?: "it is back to the smallest subsequence" [Note: ..., "additionally std::reverse(first, last)". -- End note] ---- [middle, last) MUST always be sorted, ascending order. So it should like this: "additionally std::reverse(first, last) and std::reverse(middle, last)" prev_partial_permutation: Effects: ..., "it sorts the en range in reverse order". ---- Change to ?: "it is back to the greatest subsequence" Post-condition: "is_sorted(rlast, rmiddle) or is_sorted(rlast, rmiddle, comp), where rlast is std::reverse_iterator(last) and rmiddle is std::reverse_iterator(middle)". ---- Just like next_partial_permutation, they are same, change to: "is_sorted(middle, last) or is_sorted(middle, last, comp)". [Note: ..., "additionally std::reverse(first, last)". -- End note] ---- Change to: "additionally std::reverse(first, last) and std::reverse(middle, last)" 2007/11/14, Ben Bear <benbearchen@gmail.com>:
somethings that I think must be test:
1. count of a generating circle;
2. lexicographical order;
3. finish flag;
4. smallest can next() to greatest, and greatest can prev() to smallest;
5. next() and prev(), the state should not be changed; prev() and then next(), too;
6. next generating circle should be inverted image of prev generating circle;
cross test:
1. repetition permutation is a permutation that every element is copied infinitude times;
such as next_permutation(first, first + N, 0, 4) is equal: range = {0, 0, 0, ...., 0, 1, 1, ..., 1, 2, ..., 2, 3, ..., 3} next_permutation(range.begin(), range.begin() + N, range.end());
2. completion, look up;
Examples. I think should show follows about initialization:
1. post-condition
2. how to get smallest and greatest results
Some game examples:
Drop icons. Drop icons, then count the times of right face and wrong face. This is a repetition combination.
Random build a 32bit integer. Fill a 32bit integer with 0 and 1, in random. This is repetition permutation.
Hervé: I see what your next_combination(first, last) does. I like to call it next_combination_in_count(). Your test show that for r = 5, {0, 0, 5} is the smallest. But I like {5, 0, 0} to be the smallest, if left is less than right.
I need reading the code to understand your proposal. Sorry, many words are not clear to me. So, I edited your code... Well, my test shows that, the main problems of your code are the finish flags.
The time is gone so soon... I can't write much.
If there's anything that I should do, just ask me. I'll read, read, and read the proposal.
2007/11/14, Hervé Brönnimann <hervebronnimann@mac.com>:
On Nov 13, 2007, at 10:51 PM, Ben Bear wrote:
Well, your next_permutation(first, last, first_value, last_value) should have a little change, like this: ...
Ben: Your code and mine are the same. No bugs there. As for the file that you put on the web (your next message) I will of course look at it. Before we spend too much effort on the implementation, however, I'd advise you to read and review the proposal carefully first, then read the embryo of test driver that I started, and the examples.
Once we have the test driver, we can actually verify any implementation we like, and I'll be in a better position to convince you that my implementation is correct (although it's not hard to see if you simply but carefully read the code). Of course, I'm always happy to be proven wrong - one less bug :)
Check out (be advised that programs do not yet compile/run, but if you want to work on it or can point out problem areas, I don't see why not):
http://photon.poly.edu/~hbr/boost/combinations.html http://photon.poly.edu/~hbr/boost/combination.hpp http://photon.poly.edu/~hbr/boost/combination_ex.cpp http://photon.poly.edu/~hbr/boost/combination_test.cpp
Cheers, HB _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost