Boost logo

Boost :

From: Ben Bear (benbearchen_at_[hidden])
Date: 2007-11-15 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 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_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"
>
> 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_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. 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_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