Generating combinations and permutations in C++

Posted on . Updated on .

With all these articles about the Cifras y Letras show, from time to time people seem to be hitting this website searching for C++ code that generates permutations and combinations, so this post is dedicated to every casual reader that is desperate to find out how to accomplish that task in C++. It’s very easy, but it seems some people are unable to create such an algorithm, or are so limited in time that prefer to use Google instead of writting 50 lines of code.

I apologize in advance if someone doesn’t like the following code, or thinks I should’ve used templates or object oriented design or whatever design criteria you feel a program must meet to be considered good, and I hope it’s clear enough for the people I mentioned in the first paragraph. First, the code. Then, the analysis.

Combinations

Let’s suppose you have a set of N elements in a vector and want to find all the combinations of size M (M > 0 and M ⇐ N). What do you need to do? Easy. Start by taking one element as the first one. Then, find a second element to the right of the first one, then a third element to the right of the second one, etc. Follow this method until you’ve chosen M elements. Example with elements (a, b, c), finding the combinations of two elements. The first one can be a, b or c. If it’s a, the second one can be b or c (for combinations ab and ac). If it’s b, the second one can only be c (forming bc) and if the first one is c there are no elements to its right to choose a second element. Hence, the combinations are ab, ac and bc. This isn’t rocket science.

Any algorithm that performs this task will be valid. Mine’s recursive, because I consider it easier this way. You have to search elements to the right of the previous one, and have to perform this task with M depth, so I think it calls for a recursive algorithm. Every recursive algorithm can be algorithmically transformed into an iterative algorithm, so feel free to do the conversion if you’re an iteration fan.

My test program has a recursive function, a wrapper function to simplify doing the initial call, and a main program that tests the algorithm by extracting the combinations of 3 elements out of 5. I will analyze only the recursive function.

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 requested number of 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 saves futile 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;
}

Sorry for the indentation as I’m trying to keep it narrow. The first function argument, elems, is a vector containing N elements. As you see, I chose characters as elements, just like in the examples above. The second argument, req_len, is the requested combination size or length (that is, M). pos is a vector of size req_len that will hold the positions or indexes of the chosen elements. The depth argument indicates how many elements we’ve chosen so far, that is, the recursion depth. Finally, the margin argument indicates the first position to start looking for a new element (the left "margin"). Remember we have to choose elements to the right of the last chosen one.

Simple as that, the first block checks if we’ve chosen enough elements and prints the elements in the chosen positions. If we wanted to store the combination instead of printing it, we could use one output argument, for example.

The second block checks if there are enough remaining elements to the right. In the example we put, when we chose c as the first element, there were no elements to its right to be chosen as the second one. This is a generalization of that test to stop as soon as possible. As the comments say, the function works if you remove it. However, it can be slower. This check can also be integrated into the loop condition in the third block, if you want.

The third and final block chooses one more element starting from the margin, iterating until the end of the vector, and recursively calls itself, indicating one more depth level, and setting the margin to one position to the right of the current chosen position.

The initial call must use depth 0 and margin 0.

Combinations with repetitions

I won’t spend much time with this. If elements can be repeated, you have to remove the check from the second block because there are always enough remaining elements. Finally, instead of choosing the next element strictly to the right of the last chosen one, you can start the search in the same position. This is the result:

void combinations_r_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;
  }

  // Try to select new elements in the same position or
  // to the right of the last selected one.
  for (unsigned long ii = margin; ii < elems.size(); ++ii) {
    pos[depth] = ii;
    combinations_r_recursive(elems, req_len, pos, depth + 1, ii);
  }
  return;
}

Note how I removed the second block and used ii instead of ii + 1 as the margin argument.

Permutations

Permutations are a bit trickier, but not much. After we’ve chosen one element, we must choose the new one from the whole vector. Supposing we’ve chosen b as the first element, a could be selected as the second one. Because we may have already generated ab, but we still have to generate ba. The search will start at position 0, and we can remove the margin argument. However, we must skip elements that have already been chosen. There are several ways to do this. For example, we could check the current candidate position ii is not present in the first depth elements from the pos vector. However, for the sake of being somewhat fast and making the check easier, we will use a bool vector that will indicate if a position has been already used or not, and we’re going to skip already used positions. This is the code:

void permutations_recursive(
  const vector<char> &elems,
  unsigned long req_len,
  vector<unsigned long> &pos,
  vector<bool> &used,
  unsigned long depth)
{
  // 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;
  }

  // Try to select previously unused elements.
  for (unsigned long ii = 0; ii < elems.size(); ++ii) {
    if (used[ii])
      continue;
    used[ii] = true;
    pos[depth] = ii;
    permutations_recursive(elems, req_len, pos, used, depth + 1);
    used[ii] = false;
  }
  return;
}

Note how we start the search at the initial position, we skip used elements, mark the current position as used and store it in the pos vector as we did previously. We only need to remember to clear the used flag after the recursive call, before selecting another element. Obviously, the used vector must have at least the same size as the elems vector and in the initial call all of them must be set to false.

Conclusions

That was easy, wasn’t it?

Load comments