[boost] Re: [boost] [gacap]Is any interesting to "Generating All Combinations and Permutations"£¿

From: Ben Bear (benbearchen_at_[hidden])
Date: 2007-11-14 10:29:54

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
>