A small .hpp library that can generate combinations with a focus on memory-efficiency
When generating data, it may be necessary to create a set of distinct possible combinations. This can be useful for statistics, filling up a database, or running some function over the a combination (like generating cost data given combination {x, y, z}). A lot of libraries exist to do this, but memory space can quickly run out when the amount of combinations rises to a very large number.
This library also provides the flexibility of operating on VERY large sets of data. If you have Boost installed, you can utilize its features and operate on numbers from 0 - 2^1024 - 1. (See the Installation section for more).
If you would like to see how this library was implemented, combigen is a CLI tool that helps generate distinct combinations and output them to .csv or .json format.
Input will always be a vector<vector<string>>. This keeps things nice and simple, and you can always convert back as necessary in your own projects. There are some public functions available from the library:
entry_at- Generates the nth combination at entryindexgenerate_samples- Generates a random (distinct, evenly spread out) subset of possible combinations of sizesample_sizecompute_max_size- Computes the maximum amount of possible combinationsgenerate_random_indices- Given the desired sample size and the maximum size, this function will return asetcontaining an evenly-distributed list of indices throughout the range given.
If you use the boost library, all of the above functions will instead be prepended with boost_ (see more in Example Usage).
This project is also licensed under the MIT license, so feel free to use and change this however you please.
Simply place the .hpp file somewhere in your project and include the class:
...
#include "lazy-cartesian-product.hpp"
...
using lazycp::lazy-cartesian-product; // For easier access
...
When compiling your project, ensure that it compiles to the C++14 standard (-std=c++14 flag for g++).
You will need the following installed before including this library into your project:
- C++ compiler capable of compiling to the C++14 or higher standard
- Boost if you plan to operate with large sets of data/numbers
You can also use your distro's package manager to install the necessary Boost libraries:
$ sudo apt install libboost-all-dev
$ sudo dnf install boost
$ sudo pacman -Sy boost
- Visual Studio 2015+
- Boost, either installed system-wide or you've downloaded the precompiled libraries for your system and placed them somewhere easy to remember
If you need to operate on larger sets of data, it is recommended to install the Boost library. Follow the appropriate instructions for your operating system to install boost onto your machine.
Assuming you had one file called main.cpp, you can simply compile with the following line:
$ g++ -Wall -O2 -std=c++14 -DUSE_BOOST main.cpp -lboost_random # Note: it is crucial the -lboost_random flag comes last
- Open up the x64 version of the Visual Studio compiler (usually found under Start Menu -> Visual Studio 20XX -> x64 Native Tools Command Propmpt for VS 20XX), with XX being your installed version
- Navigate to the directory where your project is located
- Assuming you are just straight-compiling your source files and downloaded the precompiled libraries, enter this command:
cl /EHsc /DUSE_BOOST /I C:\path\to\boost_1_68_0 main.cpp /link /LIBPATH:C:\path\to\boost_1_68_0\lib64-msvc-14.1
If you would like to see a more complex compilation example take a look at the combigen Makefile.
While lazy-cartesian-product can be used in many situations, below are a few examples showcasing some of the functions of the library:
First, we can generate a possible combination at the nth entry. For this example, we can find the combination of pizza components at the 5th entry.
#include <string>
#include <vector>
#include <iostream>
#include "lazy-cartesian-product.hpp" // Assumes the .hpp file is in the same directory
using std::cout;
using std::vector;
using lazycp::lazy_cartesian_product; // For easier readability
int main (int argc, char* argv[])
{
vector<string> crusts = { "Thin", "Thick", "Cheese-stuffed", "Garlic-rubbed" };
vector<string> sauces = { "Marinara", "BBQ", "None" };
vector<string> cheeses = { "Mozarella", "Cheddar", "Parmesan" };
vector<string> toppings = { "Extra Cheese", "Chicken", "Pepperoni", "Sausage" };
// Put all of the vectors together so lazy-cartesian-product can accept the input
vector<vector<string>> possibilities = { crusts, sauces, cheeses, toppings };
// Show the combination at the 5th index
vector<string> result = lazy_cartesian_product::entry_at(possibilities, 5);
// Display this result:
// "Mozarella, Thin, BBQ, Chicken, "
for (const string &entry: result)
{
cout << result << ", ";
}
cout << "\n";
return 0;
}Next, we will generate a random sample of combinations. This is especially useful for data analysis when data needs to be generated in an evenly-distributed manner. This example focuses on high-performance at the expense of memory usage (for large-computations, of course).
#include <string>
#include <vector>
#include <iostream>
#include "lazy-cartesian-product.hpp"
using std::cout;
using std::vector;
using lazycp::lazy_cartesian_product;
int main (int argc, char* argv[])
{
vector<string> crusts = { "Thin", "Thick", "Cheese-stuffed", "Garlic-rubbed" };
vector<string> sauces = { "Marinara", "BBQ", "None" };
vector<string> cheeses = { "Mozarella", "Cheddar", "Parmesan" };
vector<string> toppings = { "Extra Cheese", "Chicken", "Pepperoni", "Sausage" };
vector<vector<string>> possibilities = { crusts, sauces, cheeses, toppings };
// Generate 10 random samples
vector<vector<string>> random_samples = lazy_cartesian_product::generate_samples(possibilities, 10);
/* Displayed these results:
Mozarella, Thin, Marinara, Sausage,
Mozarella, Cheese-stuffed, Marinara, Chicken,
Mozarella, Cheese-stuffed, None, Extra Cheese,
Cheddar, Thin, None, Chicken
Cheddar, Thick, Marinara, Extra Cheese
Cheddar, Cheese-stuffed, None, Sausage
Cheddar, Garlic-rubbed, BBQ, Sausage
Cheddar, Garlic-rubbed, None, Extra Cheese
Parmesan, Thin, BBQ, Extra Cheese
Parmesan, Cheese-stuffed, BBQ, Chicken
*/
for (const vector<string> &entry: random_samples)
{
for (const string &item: entry)
{
cout << item << ", ";
}
cout << "\n";
}
return 0;
}Finally, we can generate a random sample of combinations but do so without consuming a lot of memory. By using some of the provided functions, we can sacrifice a small amount of computing time so that very little memory space is used. As such, the only limiters that remain are I/O performance and availability of disk space. This is especially useful for lower-end machines.
#include <string>
#include <vector>
#include <set>
#include <iostream>
#include "lazy-cartesian-product.hpp"
using std::cout;
using std::vector;
using std::set;
using lazycp::lazy_cartesian_product;
int main (int argc, char* argv[])
{
vector<string> crusts = { "Thin", "Thick", "Cheese-stuffed", "Garlic-rubbed" };
vector<string> sauces = { "Marinara", "BBQ", "None" };
vector<string> cheeses = { "Mozarella", "Cheddar", "Parmesan" };
vector<string> toppings = { "Extra Cheese", "Chicken", "Pepperoni", "Sausage" };
vector<vector<string>> possibilities = { crusts, sauces, cheeses, toppings };
// First, find the max size of the combinations
unsigned long long max_size = lazy_cartesian_product::compute_max_size(possiblities);
// Next, generate a list of random indices to find
set<unsigned long long> random_indices = lazy_cartesian_product::generate_random_indices(100, max_size);
// Finally, iterate through the random indices, generate a combination, and display it
for (const unsigned long long &index: random_indices)
{
vector<string> entry = lazy_cartesian_product::entry_at(possibilities, index);
for (const string &item: entry)
{
cout << item << ", ";
}
cout << "\n";
}
return 0;
}The following examples demonstrate the same functionality as above, but with the Boost library installed.
First, we can generate a possible combination at the nth entry. For this example, we can find the combination of pizza components at the 5th entry.
#include <string>
#include <iostream>
#include "lazy-cartesian-product.hpp" // Assumes the .hpp file is in the same directory
#include <boost/container/vector.hpp> // Notice how we now use the Boost libraries
using std::string;
using std::cout;
using boost::container::vector;
using lazycp::lazy_cartesian_product; // For easier readability
int main (int argc, char* argv[])
{
vector<string> crusts = { // Some REALLY big amount };
vector<string> sauces = { ... };
vector<string> cheeses = { ... };
vector<string> toppings = { ... };
// Put all of the vectors together so lazy-cartesian-product can accept the input
vector<vector<string>> possibilities = { crusts, sauces, cheeses, toppings };
// Show the combination at the 18909849082309840923850987th index
string index("18909849082309840923850987"); // Now we instead pass in a string
vector<string> result = lazy_cartesian_product::boost_entry_at(possibilities, index);
// Display result:
for (const string &entry: result)
{
cout << result << ", ";
}
cout << "\n";
return 0;
}#include <string>
#include <iostream>
#include "lazy-cartesian-product.hpp"
#include <boost/container/vector.hpp>
using std::string;
using std::cout;
using boost::container::vector;
using lazycp::lazy_cartesian_product;
int main (int argc, char* argv[])
{
vector<string> crusts = { // Some REALLY big amount };
vector<string> sauces = { ... };
vector<string> cheeses = { ... };
vector<string> toppings = { ... };
vector<vector<string>> possibilities = { crusts, sauces, cheeses, toppings };
// Generate an incredibly large sample size
string sample_size = "478928739482739877729118939847";
vector<vector<string>> random_samples = lazy_cartesian_product::boost_generate_samples(possibilities, sample_size);
for (const vector<string> &entry: random_samples)
{
for (const string &item: entry)
{
cout << item << ", ";
}
cout << "\n";
}
return 0;
}#include <string>
#include <iostream>
#include "lazy-cartesian-product.hpp"
#include <boost/container/vector.hpp>
#include <boost/container/set.hpp>
#include <boost/multiprecision/cpp_int.hpp> // Now we need the cpp_int library
using std::string;
using std::cout;
using boost::container::vector;
using boost::container::set;
using boost::multiprecision::uint1024_t; // This way we can compute the max size
using lazycp::lazy_cartesian_product;
int main (int argc, char* argv[])
{
vector<string> crusts = { // Some REALLY big amount };
vector<string> sauces = { ... };
vector<string> cheeses = { ... };
vector<string> toppings = { ... };
vector<vector<string>> possibilities = { crusts, sauces, cheeses, toppings };
// First, find the max size of the combinations
uint1024_t max_size = lazy_cartesian_product::boost_compute_max_size(possiblities);
// Next, generate a list of random indices to find (but of type uint1024_t)
string sample_size = "478928739482739877729118939847";
set<uint1024_t> random_indices = lazy_cartesian_product::boost_generate_random_indices(sample_size, max_size);
// Finally, iterate through the random indices, generate a combination, and display it
for (const uint1024_t &index: random_indices)
{
// Note: we need to convert the index to a string to find the entry_at, so we use the convert_to function
vector<string> entry = lazy_cartesian_product::boost_entry_at(possibilities, index.convert_to<string>());
for (const string &item: entry)
{
cout << item << ", ";
}
cout << "\n";
}
return 0;
}- Add better exception-handling
- Add testing framework
Pull-requests are always welcome!
MIT License
Copyright (c) 2018 Tyler Burdsall
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.