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

From: Ben Bear (benbearchen_at_[hidden])
Date: 2007-11-13 12:10:55

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 :-)

  template <typename BiIter, typename T>
  bool
  next_repeat_permutation (BiIter first, BiIter last,
                           T first_value, T last_value)
  {
    if (first == last)
      return false;

    BiIter end = last;

    while (end != first)
      {
        BiIter bi = end;
        --bi;
        T& t = ++*bi;
        if (t != last_value)
          break;

        end = bi;
      }

    std::fill (end, last, first_value);

    return end != first;
  }

Oh, your idia is beautiful :p

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'.

Another, repetitions combination:

  template <typename BiIter, typename T>
  bool
  next_repeat_combination (BiIter first, BiIter last,
                           T first_value, T last_value)
  {
    if (first == last)
      return false;

    BiIter end = last;

    T f = first_value;

    while (end != first)
      {
        BiIter bi = end;
        --bi;
        T& t = ++*bi;
        if (t != last_value)
          {
            f = t;
            break;
          }

        end = bi;
      }

    std::fill (end, last, f);

    return end != first;
  }

2007/11/13, Hervé Brönnimann <hervebronnimann_at_[hidden]>:
> 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_at_[hidden]>:
> >> 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
>