Generating Combinations in C++

Generating combinations in c++

A simple way using std::next_permutation:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, r;
    std::cin >> n;
    std::cin >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

or a slight variation that outputs the results in an easier to follow order:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n;
   std::cin >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

A bit of explanation:

It works by creating a "selection array" (v), where we place r selectors, then we create all permutations of these selectors, and print the corresponding set member if it is selected in in the current permutation of v. Hope this helps.

C++: Generate combinations in new base

This is a challenging algorithm problem. The description of the problem is misleading. A base conversion suggests that there will be a 'zero' value which would be something like this:

a, b, c, a0, aa, ab, ac, b0, b1, b2, c0, etc.

However, in this problem, 'a' represents 'zero', but 'a' also is the first digit.

Looking at this as a base conversion creates a rabbit hole of complexity.

Rather, one has to figure out the algorithm to calculate each successive digit and ignore the idea of base conversion.

The first approach is to come up with a formula for each digit, which looks like this:

int LEN = ALPHABET_LEN;  // Use a shorter variable name

std::string = ALPHABET[i % LEN];  // first digit
if(i > LEN - 1) {
  secret = ALPHABET[(i/LEN -1)%LEN] + secret;
}

if(i > LEN * (LEN+1) - 1) {
  secret = ALPHABET[(i/(LEN *(LEN+1)) - 1)%LEN] + secret;
}

if(i > LEN * (LEN+1) *(LEN+1) - 1) {
  secret = ALPHABET[(i/(LEN *(LEN+1) * (LEN+1) ) - 1)%LEN] + secret;
}

As you work out the formula for each successive digit, you realize that the base is really LEN+1 rather than LEN.

This approach works, but it always requires an additional if statement for each successive digit. Sure, for i = 1 .. 10, this works fine. But what if i = 10,000,000. It would require an endless successive series of if statements.

However, after discovering the pattern, it is now a little easier to create a while() statement that avoids the need for an endless series of if statements.

#include <iostream>
#include <string>

//works as #define, but I like string so I can easily test with 
// longer strings such as "abcd"
std::string ALPHABET {"abc"};  

int main()
{

  const int LEN = ALPHABET.size();  // Shorten the var name

  for (int i = 0; i <= 100; i++) { // use i <= 100 to verify the algorithm

    int number = i;  // save the number that we are working on for this row
    std::string secret = "";

    secret += ALPHABET[i % LEN];
    while(number / LEN > 0){
      number = number/LEN - 1;  // the base is really 4 rather than 3
      secret = ALPHABET[number%LEN] + secret;
    }
    std::cout << i << " | " << secret << std::endl;
  }
}

The output will be:

0 | a
1 | b
2 | c
3 | aa
4 | ab
5 | ac
6 | ba
7 | bb
8 | bc
9 | ca
10 | cb
11 | cc
12 | aaa
13 | aab
14 | aac
15 | aba
16 | abb
17 | abc
18 | aca
19 | acb
20 | acc
21 | baa
22 | bab
23 | bac
24 | bba
25 | bbb
26 | bbc
27 | bca
28 | bcb
29 | bcc
30 | caa
31 | cab
32 | cac
33 | cba
34 | cbb
35 | cbc
36 | cca
37 | ccb
38 | ccc
39 | aaaa
40 | aaab
41 | aaac
42 | aaba
43 | aabb
44 | aabc
45 | aaca
46 | aacb
47 | aacc
48 | abaa
49 | abab
50 | abac
51 | abba
52 | abbb
53 | abbc
54 | abca
55 | abcb
56 | abcc
57 | acaa
58 | acab
59 | acac
60 | acba
61 | acbb
62 | acbc
63 | acca
64 | accb
65 | accc
66 | baaa
67 | baab
68 | baac
69 | baba
70 | babb
71 | babc
72 | baca
73 | bacb
74 | bacc
75 | bbaa
76 | bbab
77 | bbac
78 | bbba
79 | bbbb
80 | bbbc
81 | bbca
82 | bbcb
83 | bbcc
84 | bcaa
85 | bcab
86 | bcac
87 | bcba
88 | bcbb
89 | bcbc
90 | bcca
91 | bccb
92 | bccc
93 | caaa
94 | caab
95 | caac
96 | caba
97 | cabb
98 | cabc
99 | caca
100 | cacb

Process finished with exit code 0

Generate every possible combination of a given alphabet with a given length

I am trying to make a program where the user enters a given alphabet and
length, and the program generates all possible combinations until the correct
combination is met.

If you want to match against a given combination, you should at least read it.
So, your scanf call should look like:

scanf("%s %d %s", alphabet, &len, password);

Then, you have to pass it to printAllKLengthRec and compare it with prefix when k == 0.
Function printAllKLengthRec may return an int to signal the caller there was a match with password.

Also, since you decided the max buffer length should be 256, you can avoid calling malloc by using a stack buffer to store the current combination:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int printAllKLengthRec(char const* alphabet, char* prefix, char const* password,
                       size_t alphabetLen, size_t passwordLen, size_t k) {
    if (k == 0) {
        printf("%s\n", prefix);
        return (strncmp(prefix, password, passwordLen) == 0);
    }

    int found = 0;
    for (size_t i = 0; i < alphabetLen; ++i) {
        prefix[passwordLen - k] = alphabet[i];
        found = printAllKLengthRec(alphabet, prefix, password, alphabetLen, passwordLen, k - 1);
        if (found) break;
    }

    return found;
}

const int bufsize = 256;

int main() {
    char alphabet[bufsize];
    char password[bufsize];

    /* initialize your variables */
    memset(alphabet, '\0', bufsize);
    memset(password, '\0', bufsize);
    int len = 0;

    printf("Enter alphabet, length and password:\n");
    scanf("%s %d %s", alphabet, &len, password);
    /* NOTE here you may:
     *  - evaluate len as strlen(password);
     *  - or check if the input length is actually strlen(password).
     */


    /* Use a buffer to avoid messing with malloc() in printAllKLengthRec */
    char prefix[bufsize];
    memset(prefix, '\0', bufsize);

    size_t const alphalen = strlen(alphabet);
    if (printAllKLengthRec(alphabet, prefix, password, alphalen, len, len))
        puts("found");
    else
        puts("not found");
}

generate all possible combinations of array values in C

This is how your loops unfurl at n=2, k=2:

for (i=0; i<nbr_comb; i++)
  i=0:  generate(2,0) -->   j=1:  1 mod 1 = 0
                            j=2:  2 mod 1 = 0
  i=1:  generate(2,1) -->   j=1:  1 mod 2 = 1
                            j=2:  2 mod 2 = 0
  i=2:  generate(2,2) -->   j=1:  1 mod 3 = 1
                            j=2:  2 mod 3 = 2
  i=3:  generate(2,3) -->   j=1:  1 mod 4 = 1
                            j=2:  2 mod 4 = 2
  i=4:  generate(2,4) -->   j=1:  1 mod 5 = 1
                            j=2:  2 mod 5 = 2
  i=5:  generate(2,5) -->   j=1:  1 mod 6 = 1
                            j=2:  2 mod 6 = 2
  i=6:  generate(2,6) -->   j=1:  1 mod 7 = 1
                            j=2:  2 mod 7 = 2
  i=7:  generate(2,7) -->   j=1:  1 mod 8 = 1
                            j=2:  2 mod 8 = 2
  i=8:  generate(2,8) -->   j=1:  1 mod 9 = 1
                            j=2:  2 mod 9 = 2

As you can see, your j for-loop in generate() just keeps calling modulo on j, the result of which will always be j once argument k is greater than j.

What you need is a nested for-loop that will take the current combination (range [0..(k+1)^n]) and the current array index (range [0..n-1]) into consideration when it decides which value to print from the set of [0..k].

If you think of the output as rows and columns, then in the right-most column, the value should change on each row, iterating from 0..k. In next column, the value should change every (k+1)th row. In next column, the value should change every (k+1)^2 row.

For example, when n = 3 and k = 2, then for the first 9 rows, the right-most column should look like 0,1,2,0,1,2,0,1,2. The middle column should look like 0,0,0,1,1,1,2,2,2. The left-most column should look like 0,0,0,0,0,0,0,0,0.

Thus, you end up with something like this:

   int n = 2;
   int k = 2;
   int row, col; 
   int cell;
   int rdiv;
   int nbr_comb = pow(k+1, n);

   for (row=0; row < nbr_comb; row++) 
   {
       for (col=n-1; col>=0; col--)
       {
           rdiv = pow(k+1, col);
           cell = (row/rdiv) % (k+1);
           printf("%d |", cell);
       }
       printf("\n");
   }

Fast algorithm for generating all combinations (n choose k) based on an initial input

I think the biggest problem you're going to encounter is not calculation but disk write speed or memory size. By the way, it seems you wrongly determined number of combinations for n = 250 and k = 6. Did you use uint64_t? My number is 244 140 625 000 000.

So for this number you need ~1.4 Petabyte (~1400 Tb) of memory. This is your main problem. If you have that much big hard drive, you'd better use memory mapping, when write. You may consider using several threads to write: each will write its own chunk of memory.

So, I think you should think of other ways for providing combinations for solving your actual goal.

A naive solution. Change std::ofstream with memory mapped object.

int main()
{
    const constexpr uint8_t N = 250;
    const constexpr uint8_t K = 6;
    const constexpr uint64_t CombinationsCount = std::pow(N, K);
    using TCombination = std::array<uint8_t, K>;

    std::cout << CombinationsCount << std::endl;

    std::ofstream file("output.txt");
    TCombination c;
    for (uint64_t i = 0; i < CombinationsCount; ++i)
    {
        auto I = i;
        for (auto j = 0; j < K; ++j)
        {
            c[j] = I % N;
            I /= N;
            file << (int)c[j];
        }
        file << std::endl;
    }

}

If you want to use threads, just divide CombinationsCount with cores number and give each thread a task to write from specific address of memory (offset).

You asked for a function-like solution. You can pass different names of files and use different threads. Buy you still need to use memory mapping.

const constexpr uint8_t N = 250;
const constexpr uint8_t K = 6;
const constexpr uint64_t CombinationsCount = std::pow(N, K);
using TCombination = std::array<uint8_t, K>;

void Generate(uint64_t start, uint64_t size, const char* fileName)
{
    std::ofstream file(fileName);
    TCombination c;
    for (uint64_t i = start; i < start + size; ++i)
    {
        auto I = i;
        for (auto j = 0; j < K; ++j)
        {
            c[j] = I % N;
            I /= N;
            file << (int)c[j];
        }
        file << std::endl;
    }
}

int main()
{
    std::cout << CombinationsCount << std::endl;

    unsigned int threadsNum = std::thread::hardware_concurrency();

    std::vector<std::thread> workers;
    for (size_t i = 0; i < threadsNum; ++i)
        workers.emplace_back(
            Generate, 
            i * CombinationsCount / threadsNum,
            CombinationsCount / threadsNum,
            (std::string("output") + std::to_string(i)).c_str());

    for (size_t i = 0; i < threadsNum; ++i)
        workers[i].join();
}

Generating all combinations from two lists with repetition

In my solution, I make a counter – a vector with size of first list which stores iterators in second list. Then, everything becomes very easy (and even does not need much code for implementation.)

My sample code:

#include <iostream>
#include <list>
#include <vector>

typedef std::list<char> List1;
typedef std::list<int> List2;
typedef std::vector<List2::const_iterator> Counter;

std::ostream& operator << (std::ostream &out, const std::pair<List1&, Counter&> &pair)
{
  Counter::const_iterator iter = pair.second.begin();
  for (const List1::value_type value : pair.first) {
    out << value << **iter++;
  }
  return out;
}

bool count(const List2 &lst2, Counter &counter)
{
  for (size_t i = counter.size(); i--;) {
    if (++counter[i] != lst2.end()) return false;
    counter[i] = lst2.begin();
  }
  return true; // wrap-over
}

int main()
{
  List1 lst1 = { 'a', 'b', 'c' };
  List2 lst2 = { 1, 2 };
  // make/fill counter
  std::vector<List2::const_iterator> counter(lst1.size(), lst2.begin());
  do {
    std::cout << std::pair<List1&, Counter&>(lst1, counter) << '\n';
  } while (!count(lst2, counter));
  // done
  return 0;
}

Output:

a1b1c1
a1b1c2
a1b2c1
a1b2c2
a2b1c1
a2b1c2
a2b2c1
a2b2c2

Live Demo on coliru

It's simply working like a trip meter where the first list provides number and labels of columns, and second list provides the values of columns:

---

Related Topics