[boost-users] Cartesian product

Hi,
I'm on search for an algorithm that produces the cartesian product for
n-dimension.
The coordinates of each dimension are not limited to numbers.
Ideally I'd like to write something along the lines of
std::vector<int> d0; // (assume d0 = [0, 3, 2]);
std::vector<bool> d1; // (assume d1 = [true]);
std::vectorstd::string d2; // (assume d2 = ["hello", "world"])
typedef boost::fusion::vector<
std::vector<int>,
std::vector<bool>,
std::vectorstd::string > tt;
tt space(d0, d1, d2);
boost::cartesian_product<tt> cp(space);
BOOST_FOREACH(const boost::cartesian_product<tt>::value_type &t, cp)
{
// Invoked for every possible combination of the three dimension.
// t is boost::tuple

On 10/26/11 09:46, Christoph Heindl wrote:
Hi,
I'm on search for an algorithm that produces the cartesian product for n-dimension. The coordinates of each dimension are not limited to numbers.
Ideally I'd like to write something along the lines of
std::vector<int> d0; // (assume d0 = [0, 3, 2]); std::vector<bool> d1; // (assume d1 = [true]); std::vectorstd::string d2; // (assume d2 = ["hello", "world"])
typedef boost::fusion::vector< std::vector<int>, std::vector<bool>, std::vectorstd::string > tt;
tt space(d0, d1, d2);
boost::cartesian_product<tt> cp(space);
BOOST_FOREACH(const boost::cartesian_product<tt>::value_type &t, cp) { // Invoked for every possible combination of the three dimension. // t is boost::tuple
or similar } I think that something similar can be accomplished using boost.fusion, but I cannot derive the algorithm. What I have found so far is a meta cartesian product [1].
Has anyone such an algorithm lying around? Any help would be greatly appreciated.
Best regards, Christoph
The index_stack_simple.cpp upload here: http://www.datasimfinancial.com/forum/viewtopic.php?t=416#984 shows how to do this where values in the containers are all same type. It works by simply keeping a vector of loop indices or iterators. During the operator++, it checks which which iterator to increment, and if that is at the end, then it moves to the next iterator. Dereferencing all the iterators should give 1 element in the cross product. I would think that simply changing the vector of loop indices to a fusion vector of those indices would enable the same to be done containers of different types. HTH.

On Wed, Oct 26, 2011 at 5:34 PM, Larry Evans
[...] shows how to do this where values in the containers are all same type. It works by simply keeping a vector of loop indices or iterators. During the operator++, it checks which which iterator to increment, and if that is at the end, then it moves to the next iterator. Dereferencing all the iterators should give 1 element in the cross product. I would think that simply changing the vector of loop indices to a fusion vector of those indices would enable the same to be done containers of different types.
Thanks for the hint. Actually I have something similar up and running based on code from stackoverflow. My problem stems from missing meta-programming skills. For example if we go for boost fusion, then how to get the value_type of the boost fusion vector corresponding to tuple<....>, etc... Best regards, Christoph

On 10/26/11 12:12, Christoph Heindl wrote:
On Wed, Oct 26, 2011 at 5:34 PM, Larry Evans
wrote: [...] shows how to do this where values in the containers are all same type. It works by simply keeping a vector of loop indices or iterators. During the operator++, it checks which which iterator to increment, and if that is at the end, then it moves to the next iterator. Dereferencing all the iterators should give 1 element in the cross product. I would think that simply changing the vector of loop indices to a fusion vector of those indices would enable the same to be done containers of different types.
Thanks for the hint.
Actually I have something similar up and running based on code from stackoverflow. My problem stems from missing meta-programming skills.
For example if we go for boost fusion, then how to get the value_type of the boost fusion vector corresponding to tuple<....>, etc...
Best regards, Christoph The attached code produces output:
./outer_product_seqs.exe rank=3 ops.size()=18 :i= 0:(type_u<0>=0 type_u<1>=0 type_u<2>=0) :i= 1:(type_u<0>=0 type_u<1>=0 type_u<2>=1) :i= 2:(type_u<0>=0 type_u<1>=0 type_u<2>=2) :i= 3:(type_u<0>=0 type_u<1>=1 type_u<2>=0) :i= 4:(type_u<0>=0 type_u<1>=1 type_u<2>=1) :i= 5:(type_u<0>=0 type_u<1>=1 type_u<2>=2) :i= 6:(type_u<0>=1 type_u<1>=0 type_u<2>=0) :i= 7:(type_u<0>=1 type_u<1>=0 type_u<2>=1) :i= 8:(type_u<0>=1 type_u<1>=0 type_u<2>=2) :i= 9:(type_u<0>=1 type_u<1>=1 type_u<2>=0) :i= 10:(type_u<0>=1 type_u<1>=1 type_u<2>=1) :i= 11:(type_u<0>=1 type_u<1>=1 type_u<2>=2) :i= 12:(type_u<0>=2 type_u<1>=0 type_u<2>=0) :i= 13:(type_u<0>=2 type_u<1>=0 type_u<2>=1) :i= 14:(type_u<0>=2 type_u<1>=0 type_u<2>=2) :i= 15:(type_u<0>=2 type_u<1>=1 type_u<2>=0) :i= 16:(type_u<0>=2 type_u<1>=1 type_u<2>=1) :i= 17:(type_u<0>=2 type_u<1>=1 type_u<2>=2) Compilation finished at Wed Oct 26 16:38:59 Is this what you want? It uses the g++ variadic templates compiler: http://www.generic-programming.org/~dgregor/cpp/variadic-templates.html

On 10/26/11 16:44, Larry Evans wrote: [snip]
The attached code produces output: [snip] It uses the g++ variadic templates compiler:
http://www.generic-programming.org/~dgregor/cpp/variadic-templates.html
It also uses variadic fusion from here: http://svn.boost.org/svn/boost/sandbox/SOC/2009/fusion However, I think there's a more recent variadic fusion here: https://github.com/christopherschmidt/slim , but I've not tried that one. -regards, Larry
participants (2)
-
Christoph Heindl
-
Larry Evans