A more efficient way for my program to write every billionth combination?

c++, combinations, combinatorics, permutation

Solution

I've got a simple transformation to use a different library which is about 36X faster than yours. It is still brute force. But while on my machine I'm estimating your code will take 418 days to complete, my code will take only about 3.65 days. Still outrageously long. But it gets it down to a long weekend.

Here's my code:

#include <iostream>
#include <string>
#include <fstream>
#include "../combinations/combinations"

using namespace std;

unsigned long long count = 0;

int main()
{
  ofstream myfile("m = 8.txt");

  string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnop";

  for (int i = 12; i <= 19; i++)
     for_each_combination(s.begin(), s.begin() + i, s.end(),
        [&](std::string::const_iterator f, std::string::const_iterator l) -> bool
        {
          if (::count++ % 1000000000 == 0)
            myfile << std::string(f, l) << std::endl;
          return false;
        });

  myfile.close();

  cout << "Done!" << endl;
  return 0;
}

Cutting the number of tests on `count` in the inner loop was a 15% performance increase.

"../combinations/combinations" refers to this library:

http://howardhinnant.github.io/combinations.html

The link includes a description and full source code.

This test program can also easily be modified to count the total number of combinations:

#include <iostream>
#include <string>
#include "../combinations/combinations"

using namespace std;


int main()
{
  string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnop";
  unsigned long long count = 0;
  for (int i = 12; i <= 19; i++)
     count += count_each_combination(s.begin(), s.begin() + i, s.end());

  cout << "Done! " << count << endl;
  return 0;
}

which outputs:

Done! 27189132782091

The code is open source with a boost license (it is not part of the boost library). Feel free to use it.

Problem

So the following program generates combinations on characters in this master string, which you will see in the program. First the program generates all of the 48 choose 12 combinations, and then all the way up to 48 choose 19. The problem is that the total number of combinations is 65 trillion, which is not possible to compute in a reasonable amount of time. I thought, "Ok, well I will just write every billionth one to the file." Well, that will also take a ton of time, because the program still has to count to 65 trillion, even if it only writes every billionth combination. Is there anything I could modify in my program to avoid this having to count to an extraordinary large number, but still write every billionth combination to a file? ``` #include <iostream> #include <string> #include <iostream> #include <fstream> #include <vector> using namespace std; template <typename Iterator> bool next_combination(const Iterator first, Iterator k, const Iterator last) { if ((first == last) || (first == k) || (last == k)) return false; Iterator i1 = first; Iterator i2 = last; ++i1; if (last == i1) return false; i1 = last; --i1; i1 = k; --i2; while (first != i1) { if (*--i1 < *i2) { Iterator j = k; while (!(*i1 < *j)) ++j; std::iter_swap(i1,j); ++i1; ++j; i2 = k; std::rotate(i1,j,last); while (last != j) { ++j; ++i2; } std::rotate(k,i2,last); return true; } } std::rotate(first,k,last); return false; } unsigned long long count = 0; int main() { ofstream myfile; myfile.open ("m = 8.txt"); string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnop"; for (int i = 12; i <= 19; i++) { std::size_t comb_size = i; do { if (count == 0) myfile << std::string(s.begin(),s.begin() + comb_size) << std::endl; if (++count % 1000000000 == 0) myfile << std::string(s.begin(),s.begin() + comb_size) << std::endl; }while(next_combination(s.begin(),s.begin()+ comb_size,s.end())); } myfile.close(); cout << "Done!" << endl; system("PAUSE"); return 0; } ```

Original source