Permutations act as the enchanting tool in combinatorics, enabling us to delve into the possibilities of rearranging elements within an array. Understanding the process of producing all possible permutations of an array is a valuable expertise, be it for a programmer, a mathematics enthusiast, or an individual tackling a perplexing puzzle. Within this guide, we will uncover various techniques for creating array permutations.
What does Permutations of an Array Means?
Suppose we intend to form a word using the three letters A, B, and C. These letters can be organized in different ways, referred to as permutations. The possibilities include: ABC, ACB, BAC, BCA, CBA, and CAB. Permutations emphasize the significance of the order in which elements are arranged.
The important point to note is that sometimes people mistakenly use "permutations" when they actually mean "combinations." However, there is a clear difference in the field of mathematics. Combinations consist of elements selected without considering their arrangement. For example, when we roll two dice and observe the total, the result is identical whether we roll a three and a four or a four and a three. In this scenario, the sequence is not significant.
How Many Permutations Can Be Generated?
The quantity of elements in the set or array dictates the total number of arrangements that can be generated from a specific assortment of items. The total permutations of a set containing "n" unique items selected "r" at a time can be calculated using the formula for combinations as follows:
Where:
- P(n,r) represents the number of permutations.
- n is the total number of distinct elements.
- r is the number of elements taken at a time.
- n! (read as "n factorial") represents the product of all positive integers from 1 to n .
The equation simplifies when aiming to generate all possible arrangements of a specified set (when "r" is equal to "n").
In simpler terms, it is possible to generate "n!" (n factorial) arrangements for a collection of "n" distinct parts. As the value of "n" grows, the quantity of arrangements expands rapidly. For example, there exist 3! = 6 arrangements for a group of 3 items, 4! = 24 arrangements for a group of 4 components, and so forth.
1. Using std::next_permutation from __PRESERVE_3__:
In this function, the <algorithm> header in C++ offers a practical feature for producing permutations.
Example:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> arr = {1, 2, 3};
do {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
} while (std::next_permutation(arr.begin(), arr.end()));
return 0;
}
Output:
Explanation:
In this instance, the subsequent lexicographically larger arrangement is produced using std::next_permutation. This function also indicates the absence of further permutations by returning false, serving as the foundation for this approach.
2. Recursive Backtracking:
We have the option to utilize a recursive backtracking approach to produce permutations.
Example:
#include <iostream>
#include <vector>
void generatePermutations(std::vector<int>& arr, int startIndex)
{
if (startIndex == arr.size() - 1) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return;
}
for (int i = startIndex; i < arr.size(); ++i) {
std::swap(arr[startIndex], arr[i]);
generatePermutations(arr, startIndex + 1);
std::swap(arr[startIndex], arr[i]); // Backtrack
}
}
int main() {
std::vector<int> arr = {1, 2, 3};
generatePermutations(arr, 0);
return 0;
}
Output:
Explanation:
In this instance, this method employs recursive invocations and backtracking to produce every conceivable arrangement.
3. Heap's Algorithm:
Heap's Algorithm is an iterative method designed for producing permutations by utilizing element swapping.
Example:
#include <iostream>
#include <vector>
void heapPermutation(std::vector<int>& arr, int size) {
if (size == 1) {
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return;
}
for (int i = 0; i < size; ++i) {
heapPermutation(arr, size - 1);
if (size % 2 == 1) {
std::swap(arr[0], arr[size - 1]);
} else {
std::swap(arr[i], arr[size - 1]);
}
}
}
int main() {
std::vector<int> arr = {1, 2, 3};
heapPermutation(arr, arr.size());
return 0;
}
Output:
Explanation:
In this instance, heap's Algorithm creates permutations in a non-recursive manner through the use of iterative loops and swapping operations.
