Re: [Boost-users] math: combinations of i amongst n elements

Subject: Re: [Boost-users] math: combinations of i amongst n elements
From: Clinton Mead (clintonmead_at_[hidden])
Date: 2010-10-14 22:58:11

I suggest creating a class which contains a boost::multi_array with
dimensions nCi, i.

Alternatively (or in addition), create a class with a std::vector of length
i and with a next() method and compute the combinations as you need them.

The only tricky part of this is that you need to know the datatype that the
template type iterator dereferences too. In c++0x you can do
"decltype(*iterator())" or "decltype(*begin)" or something of that effect,
but in plain c++, I'm not sure you can do any better than just passing the
datatype in as a template parameter.

e.g. in plain c++

template <typename T, typename iterator>
boost::multi_array<T, 2> combinations(iterator begin, iterator end, int i)
{
}

To call:

combinations<double>(begin, end, 3);

In C++0x probably something like this will work:

template<typename iterator>
auto combinations(iterator begin, iterator end, int i) ->
boost::multi_array<decltype(*begin), 2>
{
}

so you can just call:

combinations(begin, end, 3);

Clinton Mead

On Thu, Oct 14, 2010 at 9:39 PM, Hicham Mouline <hicham_at_[hidden]> wrote:

> Hi,
> Is there an available function to generate all the i-tuples among a
> sequence of size n (runtime) and 1<= i <=n
>
> For e.g. in a vector of 3 ints 1  2   and 3
>
> we want to get all of the singletons:
> 1
> 2
> 3
>
> all the pairs
> 1 2
> 1 3
> 2 3
>
> and all the triplets
> 1 2 3
>
> If not and I were to write one (n known at runtime only), what signature
> should I use?
>
> template <typename iterator>
> .... combinations(iterator begin, iterator end)
> {
> }
>
> what return type would hold all of the singletons, pairs, triplets, ...
> n-tuples
>
> Perhaps a better signature is
> template <typename iterator>
> .... combinations(iterator begin, iterator end, int i)
> {
> }
> but then the return type is still not easy to define.
>
> I'm thinking a 2D multi_array where not all the space is used (dim1 size is
> 2^n and dim2 size is n), and pass it by ref
>
> template <typename iterator>
> void combinations(multi_array& out, iterator begin, iterator end)
> {
> }
>
> regards,
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>