[Boost-users] mpl: generate kind of permutations

Subject: [Boost-users] mpl: generate kind of permutations
From: Hicham Mouline (hicham_at_[hidden])
Date: 2010-01-04 11:02:46

Hello,

I have 2 strictly ordered sequences of dates t1... tn, and td1...tdm, where
m and n may or may not be different.
We always have:  t1<...<tn  and td1<...<tdm.

I am trying to place the (t1...tn) sequence over the (td1...tdm) sequence,
and generate all these "permutations" ie

. all ti < td1
or. all ti < tn = td1

or. all ti except tn < td1   and (tn >td1  or tn=td2 or td3>tn>td2 or tn=td3
or ....tn>tdm-1 or tn=tdm or tn>tdm)

or. t1...tn-2 < td1 and tn-1=td1 and (td1<tn<td2 or tn=td2 or tn>td2 or
tn=td3 or ....tn>tdm-1 or tn=tdm or tn>tdm)
or. t1...tn-2 < td1 and td1<tn-1<td2 and (the same)
or. t1...tn-2 < td1 and td2=tn-1 and (the same)
...etc...etc
or. t1 < td1 and distribute the rest of t_i_s
or. t1 = td1 and distribute the rest of t_i_s
or. td2> t1 > td1 and distribute the rest of t_i_s
etc
or. tdm< t1< t2< ...<tn

I hope the description is clear enough even though it is not formal at all.

The problem is like distributing n balls over m-1 buckets or to the left or
to the right of all buckets or exactly at bucket borders (with never more
than 1 t_i on any bucket order)

In the runtime world, the pseudo-code would look like:

calling i0: number of t_is in the 0th bucket (the one to the left)
calling i1: number of t_is in the 1th bucket (between td1 and td2)
...
calling im-1: number of t_is in the (m-1)th bucket (between tdm-1 and tdm)
calling im: number of t_is in the mth bucket (>tdm)
j1 : number of t_is = td1  (0 or 1)
...
jm: number of t_is = tdm  (0 or 1)

for (i0 = n; i0>=0; --i0)
  for (i1 = n-i0; i1>=0; --i1)
    for (i2 = n-i0-i1; i2>=0; --i2)
...
     for (im = n-i0-i1-im_1; im>=0; --im)
...

0. The pseudo code is incorrect here. I need to account for the j_s as well.
1. I would normally think of using recursion to generate the serie of
inner-loops.
2. I believe there must be a purely iterative solution.
3. This problem seems familiar in that perhaps one of the STL algorithm does
something similar
4. n and m are never bigger than 4 or 5. Though already, that yields a large
number of permutations. I haven't figured out yet the exact number. So I
think compilation will be slow but not unbearably (it's a guess).
I am interested in doing this in compile-time though. I encode dates as an
ints.
I would start with the td dates the mpl::vector_c< 20100109, 20100125,
20100322, 201004228 > which gives m=4. Then I would set n to 3 for e.g. Then
I would ask the mpl metafunction to return all the possible combinations.
That would be a vector or vectors? vector_c< permut1, permumt2, ...
permut_last >

For each vector of the permut_s, I would have a runtime function to run
(chooses dates and distribute them as provided by the vector).

Regards,