next_combination: Effects: ..., ... "both [first,last) and [first, middle)" are sorted is not satisfied, ... ---- Change to: "both [first, middle) and [middle, last)" Complexity: At most "(last - first)/2" swaps. ---- Consider that smallest become greatest, should std::reverse(first, last), std::reverse(first, middle) and std::reverse(middle, last), so, should change to (?): "(last - first)" [Note: ..., "additionally std::rotate(first, middle, last)". -- End note] ---- I think std::rotate(first, middle, last) is NOT right. rotate(first, middle, last) does this: reverse(first, middle), reverse(middle, last), reverse(first, last). But combinations need this: reverse(first, last), reverse(first, middle), reverse(middle, last). It's just anti-rotate, or call it `rotate_back'? Change to: "additionally std::reverse(first, last), std::reverse(first, middle) and std::reverse(middle, last)" prev_combination: the same as next_combination "Effects: next_combination takes a sequence defined by the range [first,last) and transforms the sorted subsequence in the range [first, middle) into the next sorted subsequence of the same size from [first, last). The next sorted subsequence is found by assuming that the set of all sorted subsequences of a given size is lexicographically sorted with respect to operator< or comp. ..." I think a "combination" is a structured sequence, <first, middle, last>, having a selected subsequence and an unselected subsequence. Though a combination's value is the selected subsequence and the selected subsequence can delegate a combination, the selected subsequence's NOT a combination. Shall we say that: "... and transforms it into the next combination. The next combination is found by assuming that the set of all combination's selected subsequences of a given size ..." 2007/11/15, Ben Bear <benbearchen@gmail.com>:
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