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

From: Ben Bear (benbearchen_at_[hidden])
Date: 2008-02-02 21:22:30

2007/12/26, Hervé Brönnimann <hervebronnimann_at_[hidden]>:
> 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.

For consistency, I like this interface:

template <typename BidirectionalIterator,
          typename T,
          typename Incrementer>
  bool next_combination (BidirectionalIterator first,
                         BidirectionalIterator last,
                         T first_value, T last_value,
                         Incrementer increment);

I use this function for test:

const int LEN = 7;
int a[LEN]={0};
for (int len = 1; len < LEN; ++len)
{
  fill(a, a + len, 0);
  do
  {
    for (int i = 0; i <= len; ++i)
    {
      test_circle_permutation(a, a + i, a + len);
      test_circle_combination(a, a + i, a + len);
    }
  }
  while (next_combination(a, a + len, 0, len));
}

Repetition combination is suitable for those test.  As input data for
those tests, the elements' positions are not important.  And this
function's results can simulate all input cases with length of LEN.

Herve:  I think I lost the steps...  Shall you start a new thread for
the proposal?  This may help the discussion.