
Boost : 
From: Ben Bear (benbearchen_at_[hidden])
Date: 20071115 04:35:10
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 antirotate, 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_at_[hidden]>: > 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" > > Postcondition: "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_at_[hidden]>: > > 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. postcondition > > > > 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_at_[hidden]>: > > > > > > 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 > > > > > >
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk