Permutations and Combinations in Competitive Programming using C++

In the world of competitive programming, the application of permutations and combinations is indispensable. These concepts play a crucial role in solving algorithmic problems efficiently. In this article, we will explore the fundamentals of permutations and combinations and discuss their implementation using C++.

Permutations

A permutation refers to an arrangement of objects in a particular order. In other words, it is the number of ways we can rearrange a set of items. The formula for calculating permutations is given by:

[ ^{n}P_{r} = \frac{{n!}}{{(n-r)!}} ]

Where:

• (^{n}P_{r}) denotes the number of permutations of (n) objects taken (r) at a time.
• (n!) represents the factorial of (n), which is found by multiplying all the positive integers from (1) to (n) together.
• ((n-r)!) denotes the factorial of (n-r).

Example

Consider a scenario where we have a set of (5) numbers: ({1, 2, 3, 4, 5}). Suppose we need to find the number of permutations of length (3) that can be formed from this set. By applying the permutation formula, we get:

[ ^{5}P_{3} = \frac{{5!}}{{(5-3)!}} = \frac{{5!}}{{2!}} = 5 \times 4 = 20 ]

Therefore, there are (20) possible permutations of length (3) that can be created from the given set.

Combinations

Combinations, on the other hand, refer to the selection of objects without considering their order. In simple terms, it is the number of ways we can choose a subset from a larger set. The formula for calculating combinations is given by:

[ ^{n}C_{r} = \binom{n}{r} = \frac{{n!}}{{r! \cdot (n-r)!}} ]

Where:

• (^{n}C_{r}) denotes the number of combinations of (n) objects taken (r) at a time.
• (\binom{n}{r}) represents the binomial coefficient, which also depicts the number of ways to choose (r) objects from a set of (n) objects.
• (n!), (r!), and ((n-r)!) have the same definitions as explained earlier.

Example

Suppose we have a group of (5) students and we need to select a team of (3) students. We can use the combination formula to calculate the number of ways to form the team:

[ ^{5}C_{3} = \binom{5}{3} = \frac{{5!}}{{3! \cdot (5-3)!}} = \frac{{5!}}{{3! \cdot 2!}} = 10 ]

Hence, there are (10) possible combinations of selecting (3) students from a group of (5).

Implementation in C++

Now that we have discussed the concepts of permutations and combinations, let's see how we can implement them using C++.

Using C++ Libraries

C++ provides built-in functions in the <algorithm> library that make it easy to calculate permutations and combinations.

To generate permutations, we can use the next_permutation function, which returns the next lexicographically greater permutation of a given sequence. We can repeatedly call this function until all permutations are generated.

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

int main() {
    std::vector<int> nums = {1, 2, 3};
    // Sorting the sequence initially is necessary for generating permutations
    std::sort(nums.begin(), nums.end());

    do {
        // Process the current permutation
        for (int num : nums) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(nums.begin(), nums.end()));

    return 0;
}

To calculate combinations, we can use the next_combination function from the Boost C++ Libraries, an extensive collection of free peer-reviewed portable C++ libraries. The boost/combinatorics library must be installed and included in your project to use this function.

#include <iostream>
#include <boost/combinations.hpp>
#include <vector>

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<int> combination;

    for (int i = 1; i <= nums.size(); ++i) {
        boost::combinations_iterator<std::vector<int>::iterator> comb(nums.begin(), nums.begin() + i, nums.end());
        boost::combinations_iterator<std::vector<int>::iterator> end;

        while (comb != end) {
            combination.assign(comb->begin(), comb->end());

            // Process the current combination
            for (int num : combination) {
                std::cout << num << " ";
            }
            std::cout << std::endl;

            ++comb;
        }
    }

    return 0;
}

Using Recursion

Alternatively, we can implement permutations and combinations using recursion. Below is an example of generating permutations and combinations using recursive backtracking.

#include <iostream>
#include <vector>

void generatePermutations(std::vector<int>& nums, std::vector<int>& current, std::vector<bool>& visited) {
    // Base case: If the current permutation is of the required length, process it
    if (current.size() == nums.size()) {
        for (int num : current) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
        return;
    }

    // Recursive step: Try adding each unvisited number in the next position
    for (int i = 0; i < nums.size(); ++i) {
        if (!visited[i]) {
            visited[i] = true;
            current.push_back(nums[i]);

            generatePermutations(nums, current, visited);

            current.pop_back();
            visited[i] = false;
        }
    }
}

void generateCombinations(std::vector<int>& nums, std::vector<int>& current, int start, int k) {
    // Base case: If the current combination is of the required length, process it
    if (k == 0) {
        for (int num : current) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
        return;
    }

    // Recursive step: Try adding each number from the start index
    for (int i = start; i < nums.size(); ++i) {
        current.push_back(nums[i]);

        generateCombinations(nums, current, i + 1, k - 1);

        current.pop_back();
    }
}

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<int> current;
    std::vector<bool> visited(nums.size(), false);

    generatePermutations(nums, current, visited);
    generateCombinations(nums, current, 0, 2);

    return 0;
}

Permutations and combinations are crucial concepts to master in competitive programming. They open up a wide range of problem-solving techniques and are used in a variety of algorithms. By understanding these concepts and practicing their implementation in C++, you can enhance your problem-solving skills and excel in competitive programming.