Library Function For Permutation and Combination in C++

Library function for Permutation and Combination in C++

Combinations: from Mark Nelson's article on the same topic we have next_combination Permutations: From STL we have std::next_permutation

   template <typename Iterator>
   inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
   {
      if ((first == last) || (first == k) || (last == k))
         return false;
      Iterator itr1 = first;
      Iterator itr2 = last;
      ++itr1;
      if (last == itr1)
         return false;
      itr1 = last;
      --itr1;
      itr1 = k;
      --itr2;
      while (first != itr1)
      {
         if (*--itr1 < *itr2)
         {
            Iterator j = k;
            while (!(*itr1 < *j)) ++j;
            std::iter_swap(itr1,j);
            ++itr1;
            ++j;
            itr2 = k;
            std::rotate(itr1,j,last);
            while (last != j)
            {
               ++j;
               ++itr2;
            }
            std::rotate(k,itr2,last);
            return true;
         }
      }
      std::rotate(first,k,last);
      return false;
   }

Finding permutation and combination in C++

I used vector instead of arrays, as they are way easier to deal with.

The trick is to enumerate, in lexicographic order, the positions in the arrays, then display the values at those positions:

#include <vector>
#include <iostream>

using std::vector;

void permutate(vector<vector<int>> values)
{
    // the positions in each vector
    vector<size_t> pos(values.size());

    do
    {
        // display one of each array at current position
        for(size_t i = 0; i < values.size(); ++i)
        {
            std::cout << values[i][pos[i]] << ", ";
        }
        std::cout << std::endl;

        // increment the last array's display position
        size_t p = 0;
        pos[p]++;

        // while we get to the end of current array, return to 0 and carry to next position
        while(pos[p] == values[p].size())
        {
            pos[p] = 0;
            p++;
            pos[p]++;

            // return when the last array's position get to its size
            if (p == values.size())
            {
                return;
            }
        }
    }
    while(true);

}

int main()
{
    vector<int> arr1 = {1, 3, 8};
    vector<int> arr2 = {2, 9};
    vector<int> arr3 = {1, 3, 9};

    vector<vector<int>> allThree = {arr1, arr2, arr3};

    permutate(allThree);
}

A good exercise, next, would be to template it so you accept std::vector<std::vector<T>>

Permutation and Combination in C#

I just had a go doing this for fun, it's actually a little challenging as a naive implementation overflows long very quickly. I've included those in comments.

Equations

nPr = n! / (n - r)!
nCr = n! / r! (n - r)!

Implementaion

public static class PermutationsAndCombinations
{
    public static long nCr(int n, int r)
    {
        // naive: return Factorial(n) / (Factorial(r) * Factorial(n - r));
        return nPr(n, r) / Factorial(r);
    }

    public static long nPr(int n, int r)
    {
        // naive: return Factorial(n) / Factorial(n - r);
        return FactorialDivision(n, n - r);
    }

    private static long FactorialDivision(int topFactorial, int divisorFactorial)
    {
        long result = 1;
        for (int i = topFactorial; i > divisorFactorial; i--)
            result *= i;
        return result;
    }

    private static long Factorial(int i)
    {
        if (i <= 1)
            return 1;
        return i * Factorial(i - 1);
    }
}

Usage

Console.WriteLine(PermutationsAndCombinations.nPr(10, 3));
Console.WriteLine(PermutationsAndCombinations.nCr(10, 3));

Prints:

720
120

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.

Usage of this next_combination code

The second template argument shouldn't be bool. You can allow compiller to handle types and simply write:

while(next_combination(combo.begin(), combo.begin() + to_generate, combo.end(), std::less<int>()))
    for(std::vector<int>::iterator iter = combo.begin(); iter != combo.end() ; ++iter)
        std::cout << *iter << " ";

And use spaces - it makes code look better.

---

Related Topics