Velocity Reviews > C++ > Predictably Breaking Up a Cartesian Product

# Predictably Breaking Up a Cartesian Product

Guest
Posts: n/a

 07-15-2010
Here is some code I wrote that breaks up a Cartesian Product. It
compiles and runs fine:

#include <iostream>
#include <cmath>

void cartesian_product( const std::string& my_string, int b1, int e1 )
{

std::string::const_iterator it1, it2, it3;
std::string possibility;
possibility.reserve( 3 );

for ( it1 = my_string.begin()+b1; it1 != my_string.end()-e1; ++it1 )
{
possibility.push_back( *it1 );

for ( it2 = my_string.begin(); it2 != my_string.end(); ++it2 )
{
possibility.push_back( *it2 );

for ( it3 = my_string.begin(); it3 != my_string.end(); ++it3 )
{
possibility.push_back( *it3 );
std::cout << possibility << std::endl;
possibility.resize( 2 );
}

possibility.resize( 1 );
}
}
possibility.clear();

//// Show the break-ups
std::cout << "---" << std::endl;
}

int main ()
{
const std::string my_string ("abc"); // The string you wish to
generate the CP from.
int magic = my_string.size()-1; // Always 1 less than your string
size.
int j = 0;

// The number of character... must match number of loops in
cartesian_product()
int length = 3;
double total = pow( my_string.size(), length );
std::clog << "Total Combinations = " << total << std::endl;

// Generate CP chunks
for ( int i = magic; i >= 0; --i )
{
cartesian_product( my_string, j, i );
++j;
}
}

------------------------------

You can produce one full (unchunked) CP by doing this:

cartesian_product( my_string, 0, 0 );

I'd like to make it so that I pass an int (say 2, 3 or 4) to the
cartesian_product function so that it would produce 2, 3 or 4 chunks.
Basically control the number of chunks it produces. So for example if
there are 64 possibilities and I pass in 2, then the first run
produces the first 32 possibilities and the second the last 32. Any
suggestions?

Thanks,

Guest
Posts: n/a

 07-15-2010
On Jul 15, 11:20*am, Brad <(E-Mail Removed)> wrote:
> Here is some code I wrote that breaks up a Cartesian Product. It
> compiles and runs fine:
>
> #include <iostream>
> #include <cmath>
>
> void cartesian_product( const std::string& my_string, int b1, int e1 )
> {
>
> * * * * std::string::const_iterator it1, it2, it3;
> * * * * std::string possibility;
> * * * * possibility.reserve( 3 );
>
> * * * * for ( it1 = my_string.begin()+b1; it1 != my_string.end()-e1; ++it1 )
> * * * * {
> * * * * * * * * possibility.push_back( *it1 );
>
> * * * * * * * * for ( it2 = my_string.begin(); it2 != my_string.end(); ++it2 )
> * * * * * * * * {
> * * * * * * * * * * * * possibility.push_back( *it2 );
>
> * * * * * * * * * * * * for ( it3 = my_string.begin(); it3 != my_string.end(); ++it3 )
> * * * * * * * * * * * * {
> * * * * * * * * * * * * * * * * possibility.push_back( *it3 );
> * * * * * * * * * * * * * * * * std::cout << possibility << std::endl;
> * * * * * * * * * * * * * * * * possibility.resize( 2 );
> * * * * * * * * * * * * }
>
> * * * * * * * * * * * * possibility.resize( 1 );
> * * * * * * * * }
> * * * * }
> * * * * possibility.clear();
>
> * * * * //// Show the break-ups
> * * * * std::cout << "---" << std::endl;
>
> }
>
> int main ()
> {
> * * * * const std::string my_string ("abc"); // The string you wish to
> generate the CP from.
> * * * * int magic = my_string.size()-1; // Always 1 less than your string
> size.
> * * * * int j = 0;
>
> * * * * // The number of character... must match number of loops in
> cartesian_product()
> * * * * int length = 3;
> * * * * double total = pow( my_string.size(), length );
> * * * * std::clog << "Total Combinations = " << total << std::endl;
>
> * * * * // Generate CP chunks
> * * * * for ( int i = magic; i >= 0; --i )
> * * * * {
> * * * * * * * * cartesian_product( my_string, j, i );
> * * * * * * * * ++j;
> * * * * }
>
> }
>
> ------------------------------
>
> You can produce one full (unchunked) CP by doing this:
>
> cartesian_product( my_string, 0, 0 );
>
> I'd like to make it so that I pass an int (say 2, 3 or 4) to the
> cartesian_product function so that it would produce 2, 3 or 4 chunks.
> Basically control the number of chunks it produces. So for example if
> there are 64 possibilities and I pass in 2, then the first run
> produces the first 32 possibilities and the second the last 32. Any
> suggestions?
>
> Thanks,

Whoops... possibility.clear() is in the wrong place (I wrote that
quickly), it should be in the scope of the first for loop (moved up 2
lines). My apologies.

Francesco S. Carta
Guest
Posts: n/a

 07-15-2010
Brad <(E-Mail Removed)>, on 15/07/2010 08:20:16, wrote:

> Here is some code I wrote that breaks up a Cartesian Product. It
> compiles and runs fine:
>

<snip code>

> You can produce one full (unchunked) CP by doing this:
>
> cartesian_product( my_string, 0, 0 );
>
> I'd like to make it so that I pass an int (say 2, 3 or 4) to the
> cartesian_product function so that it would produce 2, 3 or 4 chunks.
> Basically control the number of chunks it produces. So for example if
> there are 64 possibilities and I pass in 2, then the first run
> produces the first 32 possibilities and the second the last 32. Any
> suggestions?

If you want a function that behaves depending on its previous calls you
need to give some static memory to it.

Such a function could, for example:

- store a local copy of all the incoming data;
- store an additional "progress" counter
- produce chunk_size combinations starting from progress
- update the progress counter

subsequent calls could then lookup the arguments and, if matching a
previously incomplete job, continue from there.

(all the above can be done passing chunks_number instead of chunk_size
as you request, the algorithm wouldn't be any trickier)

A functor could well done the job, maybe better, because you can throw
in additional features as, for example, querying the current progress of
a particular job, avoiding to lookup previously entered data - calling
the object with an empty pair of parentheses is just a minor, secondary

Hope these two cents help.

--
FSC - http://userscripts.org/scripts/show/59948
http://fscode.altervista.org - http://sardinias.com

Jonathan Lee
Guest
Posts: n/a

 07-15-2010
On Jul 15, 11:20*am, Brad <(E-Mail Removed)> wrote:
> Here is some code I wrote that breaks up a Cartesian Product. It
> compiles and runs fine:

[snip]

> You can produce one full (unchunked) CP by doing this:
>
> cartesian_product( my_string, 0, 0 );
>
> I'd like to make it so that I pass an int (say 2, 3 or 4) to the
> cartesian_product function so that it would produce 2, 3 or 4 chunks.
> Basically control the number of chunks it produces. So for example if
> there are 64 possibilities and I pass in 2, then the first run
> produces the first 32 possibilities and the second the last 32. Any
> suggestions?

A couple things:

As far as I can tell, you're only doing 3 dimensional products?
When I try changing it to, say, a 2 element string I get
"Total Combinations = 4" and then 8 outputs

You may want to look at Vol. 4 Fascicle 2 of Knuth's "The Art
of Computer Programming" for alternative ways of doing this.

As to your direct question you can either return the whole
(mathematical) set as a std::vector and break it up manually,
or keep a variable that increments every time you print. If
you get to (total combinations / number of blocks), output
a line and reset the counter.

--Jonathan

Guest
Posts: n/a

 07-15-2010
On Jul 15, 11:53*am, Jonathan Lee <(E-Mail Removed)> wrote:

> A couple things:
>
> *As far as I can tell, you're only doing 3 dimensional products?
> *When I try changing it to, say, a 2 element string I get
> *"Total Combinations = 4" and then 8 outputs

2 elements work fine for me:

../cartesian
Total Combinations = 8

aaa
aab
aba
abb
---
baa
bab
bba
bbb
---

> *You may want to look at Vol. 4 Fascicle 2 of Knuth's "The Art
> *of Computer Programming" for alternative ways of doing this.
>
> *As to your direct question you can either return the whole
> *(mathematical) set as a std::vector and break it up manually,
> *or keep a variable that increments every time you print. If
> *you get to (total combinations / number of blocks), output
> *a line and reset the counter.
>
> --Jonathan

Guest
Posts: n/a

 07-15-2010
On Jul 15, 11:53*am, Jonathan Lee <(E-Mail Removed)> wrote:

snip

> *As to your direct question you can either return the whole
> *(mathematical) set as a std::vector and break it up manually,

.... also forgot... big products and little memory do not go well
together.

> *or keep a variable that increments every time you print. If
> *you get to (total combinations / number of blocks), output
> *a line and reset the counter.
>
> --Jonathan

Joe Greer
Guest
Posts: n/a

 07-15-2010
Brad <(E-Mail Removed)> wrote in news:9a639db0-be5d-4982-9e01-
http://www.velocityreviews.com/forums/(E-Mail Removed):

>>
>> You can produce one full (unchunked) CP by doing this:
>>
>> cartesian_product( my_string, 0, 0 );
>>
>> I'd like to make it so that I pass an int (say 2, 3 or 4) to the
>> cartesian_product function so that it would produce 2, 3 or 4 chunks.
>> Basically control the number of chunks it produces. So for example if
>> there are 64 possibilities and I pass in 2, then the first run
>> produces the first 32 possibilities and the second the last 32. Any
>> suggestions?
>>
>> Thanks,

>
> Whoops... possibility.clear() is in the wrong place (I wrote that
> quickly), it should be in the scope of the first for loop (moved up 2
> lines). My apologies.

What about wrapping it in a function object?

Then you have all sorts of possibilities for maintaining state. Just a
thought. As a start...

struct CartesianProduct
{
CartesianProduct(int chunks = 0) : chunks_(chunks) {}
void operator()(/* some appropriate args*/)
{
// some appropriate action
}
private:
int chunks_;
// any other state data
};

CartesianProduct f(2);

f(my_string, 0);

joe

Jonathan Lee
Guest
Posts: n/a

 07-15-2010
On Jul 15, 12:02*pm, Brad <(E-Mail Removed)> wrote:
> On Jul 15, 11:53*am, Jonathan Lee <(E-Mail Removed)> wrote:
>
> > A couple things:

>
> > *As far as I can tell, you're only doing 3 dimensional products?
> > *When I try changing it to, say, a 2 element string I get
> > *"Total Combinations = 4" and then 8 outputs

>
> 2 elements work fine for me:

Ah, now that I look more closely I see I made an assumption. In
particular, that changing "length" to 2 would produce only
combinations of 2 characters.

> ... also forgot... big products and little memory do not go well
> together.

Err.. no, they don't. Hence my other suggestions.

--Jonathan

Keith H Duggar
Guest
Posts: n/a

 07-15-2010
On Jul 15, 11:20*am, Brad <(E-Mail Removed)> wrote:
> Here is some code I wrote that breaks up a Cartesian Product. It
> compiles and runs fine:
>
> #include <iostream>
> #include <cmath>
>
> void cartesian_product( const std::string& my_string, int b1, int e1 )
> {
>
> * * * * std::string::const_iterator it1, it2, it3;
> * * * * std::string possibility;
> * * * * possibility.reserve( 3 );
>
> * * * * for ( it1 = my_string.begin()+b1; it1 != my_string.end()-e1; ++it1 )
> * * * * {
> * * * * * * * * possibility.push_back( *it1 );
>
> * * * * * * * * for ( it2 = my_string.begin(); it2 != my_string.end(); ++it2 )
> * * * * * * * * {
> * * * * * * * * * * * * possibility.push_back( *it2 );
>
> * * * * * * * * * * * * for ( it3 = my_string.begin(); it3 != my_string.end(); ++it3 )
> * * * * * * * * * * * * {
> * * * * * * * * * * * * * * * * possibility.push_back( *it3 );
> * * * * * * * * * * * * * * * * std::cout << possibility << std::endl;
> * * * * * * * * * * * * * * * * possibility.resize( 2 );
> * * * * * * * * * * * * }
>
> * * * * * * * * * * * * possibility.resize( 1 );
> * * * * * * * * }
> * * * * }
> * * * * possibility.clear();
>
> * * * * //// Show the break-ups
> * * * * std::cout << "---" << std::endl;
>
> }
>
> int main ()
> {
> * * * * const std::string my_string ("abc"); // The string you wish to
> generate the CP from.
> * * * * int magic = my_string.size()-1; // Always 1 less than your string
> size.
> * * * * int j = 0;
>
> * * * * // The number of character... must match number of loops in
> cartesian_product()
> * * * * int length = 3;
> * * * * double total = pow( my_string.size(), length );
> * * * * std::clog << "Total Combinations = " << total << std::endl;
>
> * * * * // Generate CP chunks
> * * * * for ( int i = magic; i >= 0; --i )
> * * * * {
> * * * * * * * * cartesian_product( my_string, j, i );
> * * * * * * * * ++j;
> * * * * }
>
> }
>
> ------------------------------
>
> You can produce one full (unchunked) CP by doing this:
>
> cartesian_product( my_string, 0, 0 );
>
> I'd like to make it so that I pass an int (say 2, 3 or 4) to the
> cartesian_product function so that it would produce 2, 3 or 4 chunks.
> Basically control the number of chunks it produces. So for example if
> there are 64 possibilities and I pass in 2, then the first run
> produces the first 32 possibilities and the second the last 32. Any
> suggestions?

There are many ways to solve this problem. Below is one (not the
best) solution. This solution can be improved in many ways which
I leave to you as an exercise. Also note that your algorithm and
the one below outputs a multiset not a set, if that matters for

<code>
#include <cstdlib>
#include <iostream>
#include <string>

using std::string ;

int TheNumBeg ;
int TheNumEnd ;
int TheNumCur ;

void
scanToCout (
string::const_iterator i
, string::const_iterator e
) {
if ( TheNumCur >= TheNumBeg && TheNumCur < TheNumEnd ) {
for ( ; i != e ; ++i ) {
std::cout << *i ;
}
std::cout << '\n' ;
}
++TheNumCur ;
}

template <
class miter
, class citer
, class Func >
void
scanProduct (
citer const & valseti
, citer const & valsete
, miter const & bufferi
, miter const & bufferm
, miter const & buffere
, Func const & scan
) {
if ( bufferm != buffere ) {
miter buffern = bufferm ;
++buffern ;
for ( citer vi = valseti ; vi != valsete ; ++vi ) {
*bufferm = *vi ;
scanProduct(valseti,valsete,bufferi,buffern,buffer e,scan) ;
}
} else {
scan(bufferi,buffere) ;
}
}

int
main (
int argc
, char * argv[]
) {
if ( argc < 5 ) return -1 ;

string const valset(argv[1]) ;
int const bufsiz = std::atoi(argv[2]) ;
int const numbeg = std::atoi(argv[3]) ;
int const numend = std::atoi(argv[4]) ;

TheNumBeg = numbeg ;
TheNumEnd = numend ;

if ( valset.empty() ) return 0 ;

string buffer ;
buffer.resize(bufsiz>0?bufsiz:0) ;

scanProduct (
valset.begin(), valset.end()
, buffer.begin(), buffer.begin(), buffer.end()
, scanToCout
) ;

return 0 ;
}
</code>

For example to output value range [9,1

cartprod abc 3 9 18

KHD

Guest
Posts: n/a

 07-15-2010
Thanks for the tips.

I wrote some code to calculate some preliminary things. I have very
big sets (thus the use of ULL). Now I just need to write a Cartesian
Product generator that given a set, a number and a starting point will
generate that number of possibilities from that set at that starting
point. Wow, that's a mouth full.

My goal is to generate a full Cartesian Product in small pieces using
multiple CPUs while having each CPU do some calculations, rather than
one doing it all.

I appreciate all the code examples and tips. If there are any more
ideas about the generator itself, let me know. This below code works
and compiles.

#include <iostream>
#include <vector>

// Boost Includes

// To compile
g++ -static -O3 -Wall cartesian.cpp -o cartesian \

bool debug = true;

unsigned long long possibilities( std::string& n, unsigned int
length )
{
// Size of the character set to the power of length.
// pow( n ) is cleaner, but I don't want a double.
unsigned long long p = 1;
unsigned long long x = n.size();
for ( unsigned int i = 0; i < length; ++i )
{
p = x * p;
if ( debug == true )
{
std::clog << i << "\t" << p << std::endl;
}
}

if ( debug == true )
{
std::clog << "Possibilities = " << p << std::endl;
}

return p;
}

unsigned long long chunk_size( unsigned long long p, unsigned int dc )
{
// possibilities divided by the number of desired chunks.
unsigned long long cs = p/dc;

if ( debug == true )
{
std::clog << "Chunk Size = " << cs << std::endl;
}

return cs;
}

unsigned int hwt()
{
// Number of CPUs or CPU Cores in the computer
// set t manually to simulate more or less CPUs

if ( debug == true )
{
std::clog << "HWTs = " << t << std::endl;
}

return t;
}

std::vector<unsigned long long> chunks( unsigned long long p,
unsigned long long cs,
unsigned int hwt )
{
std::vector<unsigned long long> c;
c.reserve( hwt );

// Chunks match possibilities perfectly... Yeah!
if ( p % cs == 0 )
{
for ( unsigned int i = 0; i < hwt; ++i )
{
c.push_back( cs );
if ( debug == true )
{
std::clog << "Vector " << i << " Value = " << cs << std::endl;
}
}
}

// Deal with non-perfect matches
else
{
// Push all but the last chunk into the vector
for ( unsigned int i = 1; i < hwt; ++i )
{
c.push_back( cs );
if ( debug == true )
{
std::clog << "Vector " << i << " Value = " << cs << std::endl;
}
}

// Push the last chunk into the vector
unsigned long long last = cs+(p % cs);
c.push_back( last );

if ( debug == true )
{
std::clog << "Last Vector" << " Value = " << last << std::endl;
std::clog << "Addition to last vector = " << ( p % cs )<<
std::endl;
}
}

if ( debug == true )
{
std::clog << "Vector Size = " << c.size() << " (Must match HWTs)" <<
std::endl;
}

return c;
}

int main ()
{
// Make this whatever you like.
std::string my_string = "abc";

unsigned long long p = possibilities( my_string, 4 );
unsigned int t = hwt();
unsigned long long cs = chunk_size( p, t );

chunks( p, cs, t );
}