Skip to content

Instantly share code, notes, and snippets.

@rg3
Created December 7, 2010 09:43
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rg3/731626 to your computer and use it in GitHub Desktop.
Save rg3/731626 to your computer and use it in GitHub Desktop.
Simple code to create combinations in C++
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using std::copy;
using std::cout;
using std::endl;
using std::vector;
void combinations_recursive(const vector<char> &elems, unsigned long req_len,
vector<unsigned long> &pos, unsigned long depth,
unsigned long margin)
{
// Have we selected the number of required elements?
if (depth >= req_len) {
for (unsigned long ii = 0; ii < pos.size(); ++ii)
cout << elems[pos[ii]];
cout << endl;
return;
}
// Are there enough remaining elements to be selected?
// This test isn't required for the function to be correct, but
// it can save a good amount of futile function calls.
if ((elems.size() - margin) < (req_len - depth))
return;
// Try to select new elements to the right of the last selected one.
for (unsigned long ii = margin; ii < elems.size(); ++ii) {
pos[depth] = ii;
combinations_recursive(elems, req_len, pos, depth + 1, ii + 1);
}
return;
}
void combinations(const vector<char> &elems, unsigned long req_len)
{
assert(req_len > 0 && req_len <= elems.size());
vector<unsigned long> positions(req_len, 0);
combinations_recursive(elems, req_len, positions, 0, 0);
}
const unsigned long num_elements = 7;
const unsigned long comb_len = 6;
int main()
{
vector<char> elements(num_elements);
char elements_str[num_elements + 1] = "abcdefg";
copy(elements_str, elements_str + num_elements, elements.begin());
combinations(elements, comb_len);
return 0;
}
@Dominicanos
Copy link

hello, i want to ask how can i organize the element in one list, fore example elems[pos[ii]] is iqual to "ABCDEF" this like first element of one list. thank you.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment