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

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

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_at_[hidden]>:
> Sorry. I had lost too many times.
>
>
> 2007/12/6, Hervé Brönnimann <hervebronnimann_at_[hidden]>:
> > 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.
>