Re: [Boost-users] mpl: generate kind of permutations

Subject: Re: [Boost-users] mpl: generate kind of permutations
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2010-01-05 11:07:35

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