Thank you first. I'm so glad :-) 2007/11/12, Hervé Brönnimann <hervebronnimann@mac.com>:

Ben: I'm shocked to discover such a "natural" extension of prev_ and next_permutation, and that one year later it still isn't in the standard. I have a commitment to algorithms and to C++. This should definitely make it in a TR, but IMHO it's simple enough and useful enough that it should even definitely be in C++0x if there's still time.

I't simple, but not very clear. I know how it works, but I nearly can't prove and explain why. The functions are like std::next_ and prev_permutation, but the classes are not. <algorithm> has no classes. The five classes are a little like STL containers, have the [begin(), end()), but dynamic generating. Another truth, it will exist a conflict between the gacap::next_permutation(first, middle, last) and std::next_permutation(first, last, comp).

I've had success in getting the boost.minmax library into C++0x (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1990.htm), I'm proud to say it took all of ten minutes of the committee's time in Mont-Tremblant for the making the decision. I'll see if I can work on your proposal. Get in touch later.

There's no (good) proposal yeat. I think it's a hard work. Should I draft a simple proposal?

-- HB

2007/11/12, Giovanni Piero Deretta <gpderetta@gmail.com>:

This might be solvable via concepts in C++0x (or even sfinae in C++03 by detecting iteratorness)

I see it, via concepts in C++0x. It will not be a problem in C++0x.

2007/11/13, Hervé Brönnimann <hervebronnimann@mac.com>:

Ben, Giovanni: I've been giving some thought to this and I don't think that I'd want to propose next_permutation(first, middle, last) to the standard. It is easily achievable through next_combination (first, middle, last) then going over all the permutations via next_permutation(first, middle), in a loop. Granted, the order of the permutations is a bit different that way, but frankly nobody should care, the order is well specified (just not the lexicographic order on the permutations, but the lexicographic order on the underlying combination and if this combination is the same, the lexicographic order of the permutations), and it makes the would-be proposal a pure library extension -- so much easier to pass by the committee.

Then, what about next_permutation(first, middle, last, comp)? Don't propose it too? next_permutation(first, middle, last) is easy to be implemented: bool next_permutation(first, middle, last) { // actually, sort only need once, that's what init()/adjust() does sort (middle, last); reverse (middle, last); return next_permutation(first, last); } If only propose combination's functions, there's eight functions: init_combination(first, middle, last, min); init_combination(first, middle, last, min, comp); adjust_combination(first, middle, last); adjust_combination(first, middle, last, comp); next_combination(first, middle, last); next_combination(first, middle, last, comp); prev_combination(first, middle, last); prev_combiantion(first, middle, last, comp); I think that, whether the init() and adjust() can be removed, but leave the initialization to the callers, then only four functions is needed. I think this is not a good idea.

Ben: the naming partial_permutation would be a very good idea. I like it. Am I correct that your (very cute!) idea would be extended to prev_ as follows: bool next_partial_permutation(first, middle, last) { reverse (middle, last); return next_permutation(first, last); } prev_partial_permutation ( { bool result = next_permutation(first, last); reverse (middle, last); return result; } That's all good, then. BTW, you *should* assume that the client has already sorted the range. In other words, garbage in, garbage out, and that's OK. There's not reason to penalize those who keep their ranges sorted. It simply needs to be documented as a Requirement: and given again as a Post-condition: (since the functions maintain the sorted range invariant). As for the other functions, I will send you my proposal soon... HB On Nov 12, 2007, at 8:52 PM, Ben Bear wrote:

2007/11/13, Hervé Brönnimann <hervebronnimann@mac.com>:

...

Ben, Giovanni: I've been giving some thought to this and I don't think that I'd want to propose next_permutation(first, middle, last) to the standard. It is easily achievable through next_combination (first, middle, last) then going over all the permutations via next_permutation(first, middle), in a loop. Granted, the order of the permutations is a bit different that way, but frankly nobody should care, the order is well specified (just not the lexicographic order on the permutations, but the lexicographic order on the underlying combination and if this combination is the same, the lexicographic order of the permutations), and it makes the would-be proposal a pure library extension -- so much easier to pass by the committee.

Another way, why do not we change the name? The std::permutation are actually full permutation, so we can call the new one "partial permutation".

Will this make more trouble? _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost

Ben: Before you do any substantial work, please check my proposal. I have tried to provide background / explanations, and a set of coherent interfaces. Please look at: http://photon.poly.edu/~hbr/boost/combinations.html The code in the .hpp (linked) is only temporary and not debugged. I am in the process of writing test cases. I'm happy to send it to you too... Keep in mind it is work in progress. I have a job and am spending far too much time on this at the moment :) --HB PS: I am not sure about the Incrementor/Decrementor interfaces, unless I can come up with a convincing example where the underlying type is not int and does not have operator++ and operator--, but it still makes sense to count with it... On Nov 13, 2007, at 1:50 AM, Ben Bear wrote:

2007/11/13, Hervé Brönnimann <hervebronnimann@mac.com>:

...

Ben: the naming partial_permutation would be a very good idea. I like it. Am I correct that your (very cute!) idea would be extended to prev_ as follows:

bool next_partial_permutation(first, middle, last) { reverse (middle, last); return next_permutation(first, last); }

prev_partial_permutation ( { bool result = next_permutation(first, last);

oh, here should be:-) bool result = prev_permutation(first, last);

...

reverse (middle, last); return result; }

That's all good, then. BTW, you *should* assume that the client has already sorted the range. In other words, garbage in, garbage out, and that's OK. There's not reason to penalize those who keep their ranges sorted. It simply needs to be documented as a Requirement: and given again as a Post-condition: (since the functions maintain the sorted range invariant).

ok, I will prepare a resume source code that contains partial_permutation and combination, but without initializatons. It will be very simple, against gacap. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost

On Tue, Nov 13, 2007 at 04:33:51PM +0800, Ben Bear wrote:

2007/11/13, Hervé Brönnimann <hervebronnimann@mac.com>:

...

coherent interfaces. Please look at:

http://photon.poly.edu/~hbr/boost/combinations.html

I'll read this proposal. It's a little long for me.

I did so already and found two minor issue: To get all (n,r) combinations I have to specify r as value "middle". According to the document it is possible to specify r=0 but not r=n? ("Without repetitions, r is specified by a middle position in the input range [first, last) which is r positions away from first.") If r=n is possible, middle=last would be a valid choice ==> [first, last)=>[first, last]. I also do not understand "Permutations and combinations can be ordered lexicographically, starting with the subset at the first k positions of the sorted total range, and ending with the subset at the last k positions of the same range. Thus the effects of the algorithms are completely and unambiguously defined." What can be sorted? The elements of each r-tuple or do you want to say that all determined permutations and combinations are sorted (provided in a special order)? Probably you want to use r instead of k in the text above? I first thougth that I can get all values in a single r-tuple unsorted by specifying a parameter k=0 and wondered that it affects the beginning and end of some data. Could you please try to improve it a little bit? Maybe by giving some examples in the documentation? Thanks, Jens

2007/11/13, Jens Seidel <jensseidel@users.sf.net>:

Could you please try to improve it a little bit? Maybe by giving some examples in the documentation?

Oh, I wrote a php page as combination's demo, you can visit through: http://www.bxmy.org/php/combination.php You can look the php source code: http://www.bxmy.org/php/show.php?filename=combination

I put a combi_tr.zip in vault/Algorithms/combi_tr.zip. It contains three files: combination.hpp: a implementation example.cpp: a example show initialization and using test.cpp: test the combination using partial_permutation It's also available: http://www.bxmy.org/combi/combination.hpp http://www.bxmy.org/combi/example.cpp http://www.bxmy.org/combi/test.cpp About permutation and combination with repetitions, if select 4 elements from {0, 1, 2}, some code can show them: repetition permutation: for (int i = 0; i <= 2; ++i) for (int j = 0; j <= 2; ++j) for (int k = 0; k <= 2; ++k) for (int m = 0; m <= 2; ++m) { result = {i, j, k, m}; } repetition combination: for (int i = 0; i <= 2; ++i) for (int j = i; j <= 2; ++j) for (int k = j; k <= 2; ++k) for (int m = k; m <= 2; ++m) { result = {i, j, k, m}; } 2007/11/13, Hervé Brönnimann <hervebronnimann@mac.com>:

Ben: The concepts of permutations/combinations with/without repetitions are well-known and well-documented. I wouldn't want to provide too many examples for those. In any case, it would be OK and welcome to show a few instances on some actual sequences for a Boost library, but I think would be a waste of space for a C++ Standardization proposal. I think what Jens is asking for (and I intend to provide) are examples of using the proposed API to produce and use them. Thanks for your link, though. HB

On Nov 13, 2007, at 7:46 AM, Ben Bear wrote:

...

2007/11/13, Jens Seidel <jensseidel@users.sf.net>:

...

Could you please try to improve it a little bit? Maybe by giving some examples in the documentation?

Oh, I wrote a php page as combination's demo, you can visit through: http://www.bxmy.org/php/combination.php

You can look the php source code: http://www.bxmy.org/php/show.php?filename=combination _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost

---

Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

I put a implementation in: http://www.bxmy.org/combi/combination.hpp only contains "Without repetition" functions. And I'll write an example. The partial_permutation is so simple, so it's should be very solid. We can test combinations using partial_permutation. Because partial_permutation(first, middle, last)'s results contain all combination(first, middle, last)'s results, and if partial_permutation's [first, middle) is like sorted, it's a combinatin. I had do this test. A interesting of combination. We can define ONE function to replace next_ and prev_combination, that is: bool combiantion(BiIter selected_first, BiIter selected_last, BiIter unselected_first, BiIter unselected_last); Now, next_combination(first, middle, last) equal combination(first, middle, middle, last). And prev_combination(first, middle, last) equal combination(middle, last, first, middle). I'm sorry. I just can't understand your combinations and permutations with repetitions. I need time to think about this. But I think your idea is good :-) 2007/11/13, Hervé Brönnimann <hervebronnimann@mac.com>:

Ben: Good, we have half the work agreed, then. There is no way you will be able to make classes into a a standard, it is too heavy compared to a single free-standing function. This is an extension, and not a very important one, so it stands best chance for standardization if it is lightweight, crisp, and still remains useful. I also don't see what classes bring that is so much better than free functions.

And after thinking a bit, I came to the conclusion that providing the assignments from [first, last) to values in [first_value, last_value) for permutations with repetitions, and multiplicities for combinations with repetitions, was the best representation for the input/output. The user can use those to actually produce the permutations and combinations, i.e. replacing the value (iterator or integral index) by their elements pointed to in some input sequence, or copying the elements with the appropriate multiplicity, but it does away with a lot of things and simplifies the functions while retaining the core functionality. Doing otherwise would impose constraints such as CopyConstructible and Assignable for the elements of the combinations, sorted input range and EqualityComparable, etc. Not quite clear what you would do also with elements not present in some combination (multiplicity 0), but that would become present in the next combination. Etc.

Hope that helps. I'm committed now to reach the best state for this proposal, so don't be shy criticizing my proposal. If I can't defend the arguments or you have a better position, I'll be very happy that we can improve on it! --HB

Let me continue to improve the proposal, and provide examples. I

On Nov 13, 2007, at 3:33 AM, Ben Bear wrote:

...

2007/11/13, Hervé Brönnimann <hervebronnimann@mac.com>:

...

Ben: Before you do any substantial work, please check my proposal. I have tried to provide background / explanations, and a set of coherent interfaces. Please look at:

http://photon.poly.edu/~hbr/boost/combinations.html

The code in the .hpp (linked) is only temporary and not debugged. I am in the process of writing test cases. I'm happy to send it to you too... Keep in mind it is work in progress. I have a job and am spending far too much time on this at the moment :) --HB

PS: I am not sure about the Incrementor/Decrementor interfaces, unless I can come up with a convincing example where the underlying type is not int and does not have operator++ and operator--, but it still makes sense to count with it...

I agree with the eight "Without repetition" functions.

But the "With Repetition", I think that providing classes, such as class gacap::repeat_permutation, is better than functions. I had not thought how to privide functions about repetition version. It's new thing to me.

I'll read this proposal. It's a little long for me. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost

---

Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Ben: On Nov 13, 2007, at 12:10 PM, Ben Bear wrote:

I think, I know what you want to do with this function:

template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, T first_value, T last_value);

I wrote a implementation, and found that it's easy :-)

In the page I whose link I gave you, that has the documentation, I guess you didn't try to click on the link named combination.hpp. I should have pointed out that the code was available. My implementation is the same in principle, but with fewer redundant tests and assignments: template <class BidirectionalIterator, class T> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, T first_value, T last_value) { while (last != first && ++(*(--last)) == last_value) { *last = first_value; } return last != first; } As for combinations, it's not much more complicated: template <class BidirectionalIterator> bool next_combination(BidirectionalIterator first, BidirectionalIterator last) { BidirectionalIterator current = last; while (current != first && *(--current) == 0) { } if (current != first) { *(--last) = --(*current); ++*(--current); } return current != first; }

[snip] Oh, your idia is beautiful :p

Glad you like it. It's simple things that work best for me :)

I think that calling this function `next_permutation' is not good. It's very different from std::next_permutation. My `next_repeat_permutation' is also not a good name, because only I call it `repeat_permutation'.

The question of names is a good one. There is room for rationales, in the documentation page: I would have put something there about using the same name. There is no "partial" about it, this time, and I didn't have any problems naming it permutations since the signatures can't possibly be ambiguous. But perhaps a different name is a good idea. At heart, it's an assignment of values from [first,last) to [first_value, last_value). So next_assignment would be a possibility. Also since the relationship is functional, next_function or next_mapping would be possible. next_one_to_many_assignment or next_one_to_many_mapping is more precise, but too long IMHO. I don't really like any of those alternatives. It's a permutation with repetitions, but next_repetition or next_permutation_with_repetition isn't good either... In the end, I don't have anything better than next_permutation. let's hear some more suggestions... -- HB

On Nov 13, 2007, at 10:19 PM, Ben Bear wrote:

I'm sorry. I clicked the `combination.hpp' link, but it returned "404 Not Found". I thought you would put it later... `combination_ex.cpp' is also "Not Found"

Well, I didn't write the examples... But the link to hpp, the first line of the web page, where it says: Header <boost/algorithm/combination.hpp> works... I'm sorry that not all links to combination.hpp were corrected. In any case, the link is: http://photon.poly.edu/~hbr/boost/combination.hpp Cheers, -- Hervé Brönnimann hervebronnimann@mac.com

I edit your combiantion.hpp, add combination(first, last, first_value, last_value) functions, and fix some bugs. I put it at: http://www.bxmy.org/combi/hbr_combination.hpp 2007/11/14, Ben Bear <benbearchen@gmail.com>:

I have found it:-)

Well, your next_permutation(first, last, first_value, last_value) should have a little change, like this:

template <class BidirectionalIterator, class T> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, T first_value, T last_value) { while (last != first) { if (++(*(--last)) == last_value) { *last = first_value; } else { return true; } } return last != first; }

2007/11/14, Hervé Brönnimann <hervebronnimann@mac.com>:

...

On Nov 13, 2007, at 10:19 PM, Ben Bear wrote:

...

I'm sorry. I clicked the `combination.hpp' link, but it returned "404 Not Found". I thought you would put it later... `combination_ex.cpp' is also "Not Found"

Well, I didn't write the examples... But the link to hpp, the first line of the web page, where it says: Header <boost/algorithm/combination.hpp> works... I'm sorry that not all links to combination.hpp were corrected. In any case, the link is: http://photon.poly.edu/~hbr/boost/combination.hpp

Cheers, -- Hervé Brönnimann hervebronnimann@mac.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

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

Ben: Sorry for the radio silence, but time was well used. I have a full Boost library proposal articulated around your code with my modifications. I'll upload to the vault tonight... It has extensive example and full testing. I also am working on a proposal for C++0x, or the TR2 if it can't be made to squeeze in. I'm hoping Howard Hinnant will sponsor the proposal given that he's more or less proposed such a library in the past (see his web site). Howard, if you read this, I'll contact you soon. TTYS, -- Herve Bronnimann hervebronnimann@mac.com On Tuesday, December 04, 2007, at 09:10AM, "Ben Bear" <benbearchen@gmail.com> wrote:

HB: Hi. I saw that you were back. Shall we continue with the proposal? I wonder if you have time...

I update the gacap to 0.0.9.1. It contains functions discussed in the proposal. A example exam_hbr.cpp show those functions. There's no test for those functions yet. Well, I'll write some tests that are different from your, I like to wrap them.

gacap-0.0.9.1 also contains a extended version of "Generating All Combinations and Permutations". Those gacap-ex algorithms are really generating ALL combinations and permutations, the length of selected subset from 0 to N.

For example all combinations for {1, 2, 3}: {} {1} {1 2} {1 2 3} {2} {2 3} {3}

2007/11/15, Ben Bear <benbearchen@gmail.com>:

...

next_combination: Effects: ..., ... "both [first,last) and [first, middle)" are sorted is not satisfied, ... ----

---

Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Dear Ben: It's been a long day, I started at 10:30pm after just putting my kids to bed (they were still up :(... ). It was the same last night except I didn't have the energy to start working on the proposal... Time is so short... I just updated it, with the following links: 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 Most importantly (and there can be typos in other pages, but this one I've tried to get as clean as possible): http://photon.poly.edu/~hbr/boost/combination.pdf is a draft of a proposal for C++0x (if it's not too late, I'm really not sure). I think all the algorithms are worth standardizing, but maybe they'll only consider next/prev_partial_permutation, and next/ prev_combination. That'd be already a good step forward. Concerning authorship, Ben, I'd like you to be an author as well, can you send me (privately) your affiliation and any other coordinates. It might even be better if you're the principal (and perhaps even the only) author for the proposal. Cheers, -- Hervé Brönnimann hervebronnimann@mac.com PS: Howard, as promised, I put you in cc. Perhaps we should quote your web page too (http://home.twcny.rr.com/hinnant/cpp_extensions/ combinations.html)? And I'll put you in the acknowledgments since your page suggested to me the for_each... algorithms I use at the beginning of our proposal. On Dec 5, 2007, at 8:12 PM, Ben Bear wrote:

Herve: Excuse me, I just can't find the proposal in the vault. Your combination proposal page, [http://photon.poly.edu/~hbr/boost/combinations.html], is also not updated.

2007/12/4, Herve Bronnimann <hervebronnimann@mac.com>:

...

Ben: Sorry for the radio silence, but time was well used. I have a full Boost library proposal articulated around your code with my modifications. I'll upload to the vault tonight... It has extensive example and full testing.

I also am working on a proposal for C++0x, or the TR2 if it can't be made to squeeze in. I'm hoping Howard Hinnant will sponsor the proposal given that he's more or less proposed such a library in the past (see his web site). Howard, if you read this, I'll contact you soon.

TTYS, -- Herve Bronnimann hervebronnimann@mac.com

Hi Hervé,

Dear Ben: It's been a long day, I started at 10:30pm after just putting my kids to bed (they were still up :(... ). It was the same last night except I didn't have the energy to start working on the proposal... Time is so short...

I just updated it, with the following links:

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

Awesome work! Very useful. -Thorsten

Sorry. I had lost too many times. 2007/12/6, Hervé Brönnimann <hervebronnimann@mac.com>:

http://photon.poly.edu/~hbr/boost/combination.hpp

My test showed that a bug exists in prev_mapping(). The last sentence of prev_mapping() should be "return false;", but not "return true;". Date of the tested combination.hpp is 2007-12-6. I'll put my test tonight. It mainly test the increment/decrement of the sequences and the returned flags.

Hello Philip, Merry Christmas. I readed your previous submission. It's good:-) I need time to read your code. My msn is benbear1024 at hotmail dot com, if you also use msn. Another message: Herve, my test is put in vault/Algorithms/combination_test_btb.cpp. And another address: http://www.bxmy.org/combi/combinatin_test_btb.cpp I wonder if some of email I sent are lost... 2007/12/24, Philip Garofalo <philgarofalo@gmail.com>:

Hello Ben and Herve, I'm not sure if you already know but there's a previous submission for combinations and permutations (mine) in the sequence_algo folder of the sandbox. In fact, Herve helped out! :-) I've been away from it for five years. Check out the discussion thread in the archives. Nevertheless, I like your implementation. It's interesting that you chose a sorting method similar to mine, instead of using a parallel index array.

Phil Garofalo

On Dec 23, 2007 7:38 PM, Ben Bear <benbearchen@gmail.com> wrote:

...

Sorry. I had lost too many times.

2007/12/6, Hervé Brönnimann <hervebronnimann@mac.com>:

...

http://photon.poly.edu/~hbr/boost/combination.hpp

My test showed that a bug exists in prev_mapping(). The last sentence of prev_mapping() should be "return false;", but not "return true;". Date of the tested combination.hpp is 2007-12-6.

I'll put my test tonight. It mainly test the increment/decrement of the sequences and the returned flags. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Herve: I has implemented the repetition combination by count in gacap-0.0.9.1, except the name is next(prev)_repeat_combination, a little difference. It's your interface, single function and without state. I put it in vault/Algorithms/gacap-0.0.9.1.zip. The code is written in gacap-0.0.9.1/repeat_combination.hpp, and example can be found in gacap-0.0.9.1/example/exam_hbr.cpp. Well, I also copied the mainly code to vault/Algorithms/combi_count.hpp. The declaration is like this: template <typename BiIter> bool next_repeat_combination(BiIter first, BiIter last); I like the actual combinations are lexicographical order, so it's the same as other functions. And, shall we provide a transform function? template <typename ForwardIter, typename CountIter, typename T> void transform (CountIter first, CountIter last, ForwardIter value, T first_value); template <typename ForwardIter, typename CountIter, typename T, typename Incrementor> void transform (CountIter first, CountIter last, ForwardIter value, T first_value, Incrementor increase); As the times you shown, it seems like that no letter lost... :-) 2007/12/26, Hervé Brönnimann <hervebronnimann@mac.com>:

Hi Ben, and Merry Xmas to you too, slightly belatedly (although in my time zone it was still Xmas an hour ago :)

Ben, I don't know if your emails are lost, I can see as part of this thread the last messages are dated Dec 24 (11:24am, 10:27am), Dec 23 (8:38pm), Dec 8 (11:19am), Dec 7 (10:17pm, 11:31:am, 5:17am). I haven't responded as fast as usual(?) because of the holidays.

I've looked at the test code you wrote, not for very long I'm afraid. I'm glad if we both find no errors in the code.

Regarding the ordering of the sequences for combination counts, your note was very interesting. I don't know which one is more valuable, the (ordered) sequence of combination counts, or the sequence of counts such that the actual combinations are in lexicographical order. Let's make a decision, soon. One important factor (for me): Is there an implementation of your algorithm (sequence of counts such that the actual combinations are in lexicographical order) as a free function, without state? I.e., with the interface that I give in the proposal?

Cheers, -- Hervé Brönnimann hervebronnimann@mac.com

On Dec 24, 2007, at 11:23 AM, Ben Bear wrote:

...

Herve, my test is put in vault/Algorithms/combination_test_btb.cpp. And another address: http://www.bxmy.org/combi/combinatin_test_btb.cpp

I wonder if some of email I sent are lost...

---

Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Hi Ben: First of all, we missed (knowingly) the deadline for the Bellevue meeting. I am simply too busy to finish the proposal although I thought it was pretty much over before I saw your comments. About the count functions: I'm not sure I like the non-count functions anyway, and I don't think it's reasonable to provide the transform functions in a C++ standard proposal. This is not essential to C++ std lib, so it wouldn't have any support if it's too big / too much at the fringe. So if we don't like the count functions as they are, then I'd say let's take them out of the proposal and only propose the next/prev_partial_permutation and next/ prev_combination functions. Makes the proposal more focused. Nevertheless, a boost submission would have count and transform functions, that would be no problem. Cheers, -- Hervé Brönnimann hervebronnimann@mac.com On Feb 2, 2008, at 9:22 PM, Ben Bear wrote:

2007/12/26, Hervé Brönnimann <hervebronnimann@mac.com>:

...

Regarding the ordering of the sequences for combination counts, your note was very interesting. I don't know which one is more valuable, the (ordered) sequence of combination counts, or the sequence of counts such that the actual combinations are in lexicographical order. Let's make a decision, soon. One important factor (for me): Is there an implementation of your algorithm (sequence of counts such that the actual combinations are in lexicographical order) as a free function, without state? I.e., with the interface that I give in the proposal?

About Repetition Combination Interface

The Repetition Combination is useful, even for testing gacap itself.

I think that the count versions have some problems:

1. The interfaces are inconsistent with other functions. 2. A transform function is needed for converting the numbers to real values. If we don't provide this, it will be not easy to use. 3. There's two types of the numbers' lexicographic order, the numbers' or the real values'.

The count versions are beautiful, but they are not a good choice for this proposal. Users must spend more time to learn those count functions.

...

Herve: I think I lost the steps... Shall you start a new thread for the proposal? This may help the discussion. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost

Herve, my routines do include next_ and prev_partial_combination in addition to permutation fuctions. I have replaced the _r_ with _partial_ in the names. I hope that my work can contribute in any way to getting a good set of combinatorial functions into Boost. Regards, Phil Hervé Brönnimann wrote:

Ben, Phil: Merry Xmas (and to all on Boost.devel who read this thread)

Phil: LOL!!!! My reaction was identical to last time, though, so I am true to myself :) Good to talk to you again. I'm interested in your reading of the proposal, and also your evaluation of the implementation. Looking at you 2002 post again, I see I had a few more ideas for motivation (enumerating determinant minors). Also, did you have an implementation of next_(partial_)combination? Or just next_partial_permutation (next_r_permutation in your naming scheme).

Re: Names: I still don't like next_r_permutation, and think we've struck a better name with next_partial_permutation. Any other suggestions?

Pending a few clean-ups and more testing I'll do following Ben's messages this week (I've got a few days off work) the plan is to submit something to the Standard Library Committee for the Bellevue, Wash. meeting, with C++0x as a target (or TR2 if if 0x is not feasible).

For now, ciao, -- Hervé Brönnimann hervebronnimann@mac.com

On Dec 23, 2007, at 11:33 PM, Philip Garofalo wrote:

...

Hello Ben and Herve, I'm not sure if you already know but there's a previous submission for combinations and permutations (mine) in the sequence_algo folder of the sandbox. In fact, Herve helped out! :-) I've been away from it for five years. Check out the discussion thread in the archives. Nevertheless, I like your implementation. It's interesting that you chose a sorting method similar to mine, instead of using a parallel index array.

Phil Garofalo

On Dec 23, 2007 7:38 PM, Ben Bear <benbearchen@gmail.com> wrote:

...

Sorry. I had lost too many times.

2007/12/6, Hervé Brönnimann <hervebronnimann@mac.com>:

...

http://photon.poly.edu/~hbr/boost/combination.hpp My test showed that a bug exists in prev_mapping(). The last sentence of prev_mapping() should be "return false;", but not "return true;". Date of the tested combination.hpp is 2007-12-6.

I'll put my test tonight. It mainly test the increment/decrement of the sequences and the returned flags. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost

---

Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Philip: Yeah, I think our methods are same. Well, the unselected elements are sorted makes the algorithm easy to be implemented and more quicker. Sorry, I don't know what's parallel index array ;-( I read the defination of "Parallel array" in wikipedia... Does it like iterator to iterator?? 2007/12/24, Philip Garofalo <philgarofalo@gmail.com>:

Hello Ben and Herve, I'm not sure if you already know but there's a previous submission for combinations and permutations (mine) in the sequence_algo folder of the sandbox. In fact, Herve helped out! :-) I've been away from it for five years. Check out the discussion thread in the archives. Nevertheless, I like your implementation. It's interesting that you chose a sorting method similar to mine, instead of using a parallel index array.

Phil Garofalo

On Dec 23, 2007 7:38 PM, Ben Bear <benbearchen@gmail.com> wrote:

...

Sorry. I had lost too many times.

2007/12/6, Hervé Brönnimann <hervebronnimann@mac.com>:

...

http://photon.poly.edu/~hbr/boost/combination.hpp

My test showed that a bug exists in prev_mapping(). The last sentence of prev_mapping() should be "return false;", but not "return true;". Date of the tested combination.hpp is 2007-12-6.

I'll put my test tonight. It mainly test the increment/decrement of the sequences and the returned flags. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Phil, Hi! Make them sorted, so we know more information about the input sequence. It's easy to find the max or min elements. All those lexicographical ordered algorithms have to find most greatest or smallest needed element. gacap provides three types interface: - functions, like std::next_permutation - direct classes, wrapper of functions - indirect classes, work at the iterators but not the elements directly, wrapper of classes direct. I think this is like the parallel index array. Well, Herve' proposal may only contains part functions, but boost may aceept more :-) 2007/1/16, Phil Garofalo <philgarofalo@gmail.com>:

Ben, Apologies for the late response. I haven't run GACAP yet, but sorting the unselected elements sounds right. I am a bit surprised that keeping them sorted doesn't essentially have the same cost. Again, I will look at your implementation more closely.

The parallel index array approach is describe in the book _Discrete Mathematics_ by Johnsonbaugh. It essentially creates an integer array of the same size as the input container as indexes into the container, and then sorts as appropriate through the integers (less costly comparisons). I didn't implement it because directly manipulating the container seems more elegant and not that much more costly.

Regards,

Phil

Ben Bear wrote:

...

Philip: Yeah, I think our methods are same. Well, the unselected elements are sorted makes the algorithm easy to be implemented and more quicker.

Sorry, I don't know what's parallel index array ;-( I read the defination of "Parallel array" in wikipedia... Does it like iterator to iterator??

2007/12/24, Philip Garofalo <philgarofalo@gmail.com>:

...

Hello Ben and Herve, I'm not sure if you already know but there's a previous submission for combinations and permutations (mine) in the sequence_algo folder of the sandbox. In fact, Herve helped out! :-) I've been away from it for five years. Check out the discussion thread in the archives. Nevertheless, I like your implementation. It's interesting that you chose a sorting method similar to mine, instead of using a parallel index array.

Phil Garofalo

On Dec 23, 2007 7:38 PM, Ben Bear <benbearchen@gmail.com> wrote:

...

Sorry. I had lost too many times.

2007/12/6, Hervé Brönnimann <hervebronnimann@mac.com>:

...

http://photon.poly.edu/~hbr/boost/combination.hpp My test showed that a bug exists in prev_mapping(). The last sentence of prev_mapping() should be "return false;", but not "return true;". Date of the tested combination.hpp is 2007-12-6.

I'll put my test tonight. It mainly test the increment/decrement of the sequences and the returned flags. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Herve: Merry Christmas When I wrote test for next(prev)_combination_counts, I found a difference with us. (Well, the version is also 2007-12-6) I want to transform the `data' sequence, which is argument of next_combination_counts, to the `value' sequence, which is the result like next_mapping()'s output. But found that the data sequences are lexicographical order, while the value sequences are not. First, see the transforms. For example, the srouce values are {1, 2, 3, 4}, so the data sequence should have 4 elements, such as int data[4]; the size of value sequence is 5, such as int value[5]. (The transform order is reversed, so the data[4]={0, 0, 0, 5} will means the smallest value sequence value[5]={1, 1, 1, 1, 1}.) data[4] = {1, 1, 1, 2} <==> value[5] = {1, 1, 2, 3, 4} void transform() { int* v = value; int sv = 1; // source value for (int* di = data + 4; di != data;) { --di; for (int i = 0; i < *di; ++i) *v++ = sv; ++sv; } } With your implement, the example will be: value sequence data sequence 1 1 1 1 1 0 0 0 5 1 1 1 1 2 0 0 1 4 1 1 1 2 2 0 0 2 3 1 1 2 2 2 0 0 3 2 1 2 2 2 2 0 0 4 1 2 2 2 2 2 0 0 5 0 1 1 1 1 3 0 1 0 4 ... My implement like this: (transform order is not reversed.) value:[1 1 1] data: 3 0 0 value:[1 1 2] data: 2 1 0 value:[1 1 3] data: 2 0 1 value:[1 2 2] data: 1 2 0 value:[1 2 3] data: 1 1 1 value:[1 3 3] data: 1 0 2 value:[2 2 2] data: 0 3 0 value:[2 2 3] data: 0 2 1 value:[2 3 3] data: 0 1 2 value:[3 3 3] data: 0 0 3 The value sequences are lexicographical order, while the data sequences are not. 2007/12/24, Ben Bear <benbearchen@gmail.com>:

Sorry. I had lost too many times.

2007/12/6, Hervé Brönnimann <hervebronnimann@mac.com>:

...

http://photon.poly.edu/~hbr/boost/combination.hpp

My test showed that a bug exists in prev_mapping(). The last sentence of prev_mapping() should be "return false;", but not "return true;". Date of the tested combination.hpp is 2007-12-6.

I'll put my test tonight. It mainly test the increment/decrement of the sequences and the returned flags.

Herve: I'm here. I had a look at the proposal. I think some references can be added. Such as: http://www.bxmy.org/article/combination.pdf http://www.bxmy.org/php/combination.php http://www.codeproject.com/KB/recipes/CombC.aspx I will read it tonight. 2008/5/19 Hervé Brönnimann <hervebronnimann@mac.com>:

Ben, Phil: I'm reviving this thread, because tomorrow is the deadline for the next C++ Std meeting (Sophia-Antipolis). I decided I would make that deadline. The proposal hasn't changed much, hopefully, it's cleaner / bug-free, and I have left the count versions in the proposal, but they can be voted on separately. I've put in the illustration/examples b/c I think without it there will be too many questions. I think the next/prev mapping is useful no matter what, perhaps in a different section of Ch 25, <algorithm> (it doesn't have much in that formulation to do with sorting). I'll let the committee decide.

Check out the latest version:

http://photon.poly.edu/~hbr/boost/combination.pdf

Cheers, -- Hervé Brönnimann hervebronnimann@mac.com

On Dec 4, 2007, at 9:10 AM, Ben Bear wrote:

...

Hi. I saw that you were back. Shall we continue with the proposal? I wonder if you have time...

---

Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost