mpl: generate kind of permutations
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,
Hicham Mouline wrote:
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
<snip examples>
I hope the description is clear enough even though it is not formal at all.
I'm sorry, maybe I wasn't trying hard enough to understand what you're trying to build here. I'm left with a hazy impression that you want to construct a merged sequence of dates, possibly including tag information identifying the original sequence from which a particular date came. But my notion of merge processing includes the idea of "consuming" items from the input sequences. I don't know how I'd attempt to implement that at compile time. Then again, I'm the wrong person to ask about MPL. Essentially I'm responding that no, I really didn't understand your problem statement. Perhaps a clearer restatement would prompt useful suggestions from others?
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Nat Goodspeed Sent: 05 January 2010 3:47 To: boost-users@lists.boost.org Subject: Re: [Boost-users] mpl: generate kind of permutations
Hicham Mouline wrote:
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
<snip examples>
I hope the description is clear enough even though it is not formal at all.
I'm sorry, maybe I wasn't trying hard enough to understand what you're trying to build here. I'm left with a hazy impression that you want to construct a merged sequence of dates, possibly including tag information identifying the original sequence from which a particular date came.
But my notion of merge processing includes the idea of "consuming" items from the input sequences. I don't know how I'd attempt to implement that at compile time. Then again, I'm the wrong person to ask about MPL.
Essentially I'm responding that no, I really didn't understand your problem statement. Perhaps a clearer restatement would prompt useful suggestions from others? Taking my example from before, starting the dates vector with YYYYMMDD int elements mpl::vector_c< 20100109, 20100125, 20100322, 20100428 > tds; // requires strictly sorted elements
and I want to place n=3 dates in buckets formed by the above 4 dates. Let's say the way I choose the dates is 1 day, then 2 day, then 3days, less the dates in tds. So I want the metafunction to return the list of all mpl::vector_c<> that have always 3 elements strictly sorted, so that . all 3 dates < 20100109 ( 20100106 20100107 20100108 ) . 2 dates < 20100109 and 3rd date=20100109 ( 20100107 20100108 20100109 ) . ( 20100107 20100108 20100110 ) . ( 20100107 20100108 20100125 ) . ( 20100107 20100108 20100126 ) . ( 20100107 20100108 20100322 ) . ( 20100107 20100108 20100323 ) . ( 20100107 20100108 20100428 ) . ( 20100107 20100108 20100429 ) . 1 date < 20100109 and 2dates>=20100109 ( 20100108 20100109 20100110 ) . ( 20100108 20100109 20100125 ) . ( 20100108 20100109 20100126 ) . ( 20100108 20100109 20100322 ) . ( 20100108 20100109 20100323 ) . ( 20100108 20100109 20100428 ) . ( 20100108 20100109 20100429 ) . ( 20100108 20100110 20100111 ) . ( 20100108 20100110 20100125) . ( 20100108 20100110 20100126 ) . ( 20100108 20100110 20100322 ) . ( 20100108 20100110 20100323 ) . ( 20100108 20100110 20100428 ) . ( 20100108 20100110 20100429 ) Etc Etc 0 date<20100109 and 3dates>=20100109 The objective is to write the metafunction for generic tds vector, and generic n (not just 3) I hope this is clearer otherwise, I will write the complete list next time. Regards,
AMDG Hicham Mouline wrote:
Taking my example from before, starting the dates vector with YYYYMMDD int elements mpl::vector_c< 20100109, 20100125, 20100322, 20100428 > tds; // requires strictly sorted elements
and I want to place n=3 dates in buckets formed by the above 4 dates.
Let's say the way I choose the dates is 1 day, then 2 day, then 3days, less the dates in tds.
So I want the metafunction to return the list of all mpl::vector_c<> that have always 3 elements strictly sorted, so that
. all 3 dates < 20100109 ( 20100106 20100107 20100108 )
. 2 dates < 20100109 and 3rd date=20100109 ( 20100107 20100108 20100109 ) . ( 20100107 20100108 20100110 ) . ( 20100107 20100108 20100125 ) . ( 20100107 20100108 20100126 ) . ( 20100107 20100108 20100322 ) . ( 20100107 20100108 20100323 ) . ( 20100107 20100108 20100428 ) . ( 20100107 20100108 20100429 )
. 1 date < 20100109 and 2dates>=20100109 ( 20100108 20100109 20100110 ) . ( 20100108 20100109 20100125 ) . ( 20100108 20100109 20100126 ) . ( 20100108 20100109 20100322 ) . ( 20100108 20100109 20100323 ) . ( 20100108 20100109 20100428 ) . ( 20100108 20100109 20100429 )
. ( 20100108 20100110 20100111 ) . ( 20100108 20100110 20100125) . ( 20100108 20100110 20100126 ) . ( 20100108 20100110 20100322 ) . ( 20100108 20100110 20100323 ) . ( 20100108 20100110 20100428 ) . ( 20100108 20100110 20100429 ) Etc Etc
0 date<20100109 and 3dates>=20100109
The objective is to write the metafunction for generic tds vector, and generic n (not just 3)
I hope this is clearer otherwise, I will write the complete list next time.
Something like this should generate all subsets of a sequence of a specific size. (Warning completely untested) template<class Seq, class N> struct subset; template<class Seq, class N> struct subset_recurse { typedef typename boost::mpl::pop_front<Seq>::type next; typedef typename subset<next, N>::type result; typedef typename subset<next, typename boost::mpl::prior<N>::type>::type extra; typedef typename boost::mpl::transform<extra, boost::mpl::push_front<_1, typename boost::mpl::front<Seq>::type>, boost::mpl::back_inserter<result> >::type type; }; template<class Seq, class N> struct subset { typedef typename boost::mpl::eval_if<boost::mpl::equal_to<boost::mpl::size<Seq>, N>, boost::mpl::vector1<Seq>, boost::mpl::eval_if<boost::mpl::equal_to<N, boost::mpl::int_<0> >, boost::mpl::vector1<boost::mpl::vector0<> >, subset_recurse<Seq, N> > >::type type; }; In Christ, Steven Watanabe
participants (3)
-
Hicham Mouline -
Nat Goodspeed -
Steven Watanabe