Iterators for the cartesian product
So that the wheel doesn't have to be reinvented if it's already out there, is there something in boost that will take a bunch of sequences (lists, say) and return a sequence containing the cartesian product all of them, either as a tuple or after applying a function to them? For example, is there something in boost that will, given a bunch of lists of integers, return a list of integers formed by multiplying together one member from each list?
On 06/13/11 06:37, kelvSYC wrote:
So that the wheel doesn't have to be reinvented if it's already out there, is there something in boost that will take a bunch of sequences (lists, say) and return a sequence containing the cartesian product all of them, either as a tuple or after applying a function to them?
For example, is there something in boost that will, given a bunch of lists of integers, return a list of integers formed by multiplying together one member from each list?
To be more concrete, say you have: std::vector<int> x({1,2,3}); std::vector<int> y({4,5}); and what you want is something like: std::vector<std::vector<int> > z ( { { 4, 5} , { 8, 10} , { 12, 15} } }; Is that about right? If so, then this is also called outer_product (at least in apl that's what it's called): http://en.wikipedia.org/wiki/Outer_product I'm guessing this is also closely related to list comprehension in haskell: http://www.haskell.org/haskellwiki/List_comprehension There is some code in boost's vault which was announced on the boost developer's mailing list in December 2010. http://thread.gmane.org/gmane.comp.lib.boost.devel/211905/focus=211919 HTH. -regards, Larry
On Jun 13, 2011, at 8:19 AM, Larry Evans wrote:
On 06/13/11 06:37, kelvSYC wrote:
So that the wheel doesn't have to be reinvented if it's already out there, is there something in boost that will take a bunch of sequences (lists, say) and return a sequence containing the cartesian product all of them, either as a tuple or after applying a function to them?
For example, is there something in boost that will, given a bunch of lists of integers, return a list of integers formed by multiplying together one member from each list?
To be more concrete, say you have:
std::vector<int> x({1,2,3}); std::vector<int> y({4,5});
and what you want is something like:
std::vector<std::vector<int> > z ( { { 4, 5} , { 8, 10} , { 12, 15} } };
Is that about right?
No, just a straight up cartesian product. So I'd want z to be equal to std::vector<std::vector<int>>({{1,4}, {1,5}, {2,4}, {2,5}, {3,4}, {3,5}}); Is there something in boost that will give me this sequence (or at least iterators therein?)
On 06/13/11 15:06, kelvSYC wrote:
On Jun 13, 2011, at 8:19 AM, Larry Evans wrote:
On 06/13/11 06:37, kelvSYC wrote:
So that the wheel doesn't have to be reinvented if it's already out there, is there something in boost that will take a bunch of sequences (lists, say) and return a sequence containing the cartesian product all of them, either as a tuple or after applying a function to them?
For example, is there something in boost that will, given a bunch of lists of integers, return a list of integers formed by multiplying together one member from each list?
To be more concrete, say you have:
std::vector<int> x({1,2,3}); std::vector<int> y({4,5});
and what you want is something like:
std::vector<std::vector<int> > z ( { { 4, 5} , { 8, 10} , { 12, 15} } };
Is that about right?
No, just a straight up cartesian product.
The example I provided was meant to be an example of, as you say, "applying a function to them". In my example, that would be the std::multiply<int>() functor. The "straight up cartesian product" would be produced by using std::make_pair<int,int> as the function.
So I'd want z to be equal to
std::vector<std::vector<int>>({{1,4}, {1,5}, {2,4}, {2,5}, {3,4}, {3,5}});
Is there something in boost that will give me this sequence (or at least iterators therein?)
I pretty sure there is none since the thread I mentioned previously did not mention one and people replying to that thread indicated it would be desirable. -regards, Larry
On 06/13/11 15:25, Larry Evans wrote:
On 06/13/11 15:06, kelvSYC wrote:
On Jun 13, 2011, at 8:19 AM, Larry Evans wrote:
[snip]
So I'd want z to be equal to
std::vector<std::vector<int>>({{1,4}, {1,5}, {2,4}, {2,5}, {3,4}, {3,5}});
Is there something in boost that will give me this sequence (or at least iterators therein?)
I pretty sure there is none since the thread I mentioned previously did not mention one and people replying to that thread indicated it would be desirable.
The attached code, using boost multi_array, produces output shown in 2nd attachment. It does use some utility functions for printing out the mult_array, but I'm sure you could roll-your-own without much problem. The interesting thing is that it will work for not just vectors, but any dimension multi_array; however, I think it depends on the multi_array's being in c_storage_order. I tried inner_product with the code from the Budd book; however, that failed to get the right answer for fortran_storage order. The last result output is simply a flattened version of the immediately preceding result output. I think that last output is closer to the std::vector<std::vector<int> > form you showed previously. HTH. -Larry
On 06/13/11 17:54, Larry Evans wrote:
On 06/13/11 15:25, Larry Evans wrote:
On 06/13/11 15:06, kelvSYC wrote:
On Jun 13, 2011, at 8:19 AM, Larry Evans wrote:
[snip]
So I'd want z to be equal to
std::vector<std::vector<int>>({{1,4}, {1,5}, {2,4}, {2,5}, {3,4}, {3,5}});
Is there something in boost that will give me this sequence (or at least iterators therein?)
I pretty sure there is none since the thread I mentioned previously did not mention one and people replying to that thread indicated it would be desirable.
The attached code, using boost multi_array, produces output shown in 2nd attachment. [snip] The attached code produces same output but is clearer and probably faster because, instead of using div, it just uses ++, although it does have 2 loops instead of just one.
On 13 June 2011 12:37, kelvSYC <kelvsyc@gmail.com> wrote:
So that the wheel doesn't have to be reinvented if it's already out there, is there something in boost that will take a bunch of sequences (lists, say) and return a sequence containing the cartesian product all of them, either as a tuple or after applying a function to them?
For example, is there something in boost that will, given a bunch of lists of integers, return a list of integers formed by multiplying together one member from each list?
It seems that the folks at Organic Vectory have solved a problem along these lines: http://www.organicvectory.com/index.php?option=com_content&view=article&id=75:boostmplcartesianproduct&catid=42:boost&Itemid=78 They make use of the Boost MPL, which would provide you with tools for implementing your own solution if you don't find an implementation you like.
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (3)
-
eddyaod＠gmail.com -
kelvSYC -
Larry Evans