Re: Predictably Breaking Up a Cartesian Product

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
#include <boost/thread/thread.hpp>

// To compile
g++ -static -O3 -Wall cartesian.cpp -o cartesian \
-I/usr/local/include/boost-1_43 /usr/local/lib/libboost_thread-mt.a \
-pthread

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
    unsigned int t = boost::thread::hardware_concurrency();

    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 );
}