# 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.