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

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

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

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

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

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;
}
```

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.

noob to master © copyleft