In this guide, you will discover the process of displaying all permutations in a sorted manner using C++, along with an illustrative example. Prior to delving into the coding aspect, it is essential to grasp the concepts of permutations and lexicographic order within the realm of C++.
What are Permutations?
A core concept in the realm of computer science and combinatorics is permutations. Permutations refer to collections of objects organized in a specific order, and a frequent task in designing algorithms involves identifying all feasible permutations of a group of items.
What is Lexicographic Order?
Lexicographic order is an arrangement of the elements according to their alphabetical order ; it is often referred to as dictionary order or alphabetical order. As it pertains to permutations, Lexical order places them in the same order as words in a dictionary.
- For instance, take into consideration the set {A, B, C} .
- The permutations are listed in the following lexicographic order: ABC ACB BAC BCA CAB CBA
- The goal is to produce all possible character combinations for a string of length n in a sorted order.
- Consider the following example to further grasp the issue: Enter "XYZ" XYZ, XZY, YXZ, YZX, ZXY, ZYX are the outputs.
- In this case, all permutations must be printed in lexicographical order, which is an alphabetically increasing order.
- Enter "XYZ"
- XYZ, XZY, YXZ, YZX, ZXY, ZYX are the outputs.
The arranged array serves as the starting point for the permutation. Therefore, sorting it in alphabetical order is the primary action required to tackle this issue. Following this, it generates the subsequent permutation of the string.
You can gain a deeper understanding of the resolution by examining the following code snippet:
#include<iostream>
#include<string.h>
using namespace std;
int compare(const void *a, const void * b){
return ( *(char *)a - *(char *)b );
}
void swap(char* a, char* b) {
char t = *a;
*a = *b;
*b = t;
}
int finduBound(char str[], char first, int l, int h) {
int ubound = l;
for (int i = l+1; i <= h; i++)
if (str[i] > first && str[i] < str[ubound])
ubound = i;
return ubound;
}
void generatePermutaion ( char str[] ) {
int size = strlen(str);
qsort( str, size, sizeof( str[0] ), compare );
bool isFinished = false;
while ( ! isFinished ) {
cout<<str<<"\t";
int i;
for ( i = size - 2; i >= 0; --i )
if (str[i] < str[i+1])
break;
if ( i == -1 )
isFinished = true;
else {
int ubound = finduBound( str, str[i], i + 1, size - 1 );
swap( &str[i], &str[ubound] );
qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
}
}
}
int main() {
char str[] = "NOPQ";
cout<<"Permutation in Sorted order:\n";
generatePermutaion(str);
return 0;
}
Output:
Code Explanation:
The provided C++ code creates and outputs, in lexicographic sequence, every variation of a given string. The reasoning employed in the code is explained as follows:
- When sorting, characters are compared using the compare function. It is a common comparison function from the C Standard Library that can be used with qsort .
- In the string, two characters can be switched using the swap function .
- Within a given range of the string, the finduBound function locates the rightmost character that is smaller than a particular character first. This function is used to determine which character in the string should be swapped out for the character at position i .
- After sorting the input text using qsort to place it in lexicographical order, the generatePermutation function creates and prints every permutation in the sorted order.
- "NOPQ" is an example string that is fed into the main function.
- The message printed by the main function indicates that permutations will be printed in sorted order.
- After that, the function generatePermutation is called, passing in the input text "NOPQ".
Creating permutations in lexicographical order is the core concept of this algorithm. To produce the next permutation, the algorithm involves swapping characters while ensuring the string remains sorted throughout. This process continues until all possible combinations have been generated and displayed. The resulting output demonstrates the algorithm's ability to systematically produce every possible permutation of the given string in lexicographical order.
Example Program:
#include <iostream>
#include <algorithm>
void generateCombinations(std::string str) {
std::sort(str.begin(), str.end()); // Sort the input string
do {
std::cout << str << std::endl; // Output the current combination
} while (std::next_permutation(str.begin(), str.end())); // Generate the next lexicographically greater permutation
}
int main() {
std::string input = "XYZ";
generateCombinations(input);
return 0;
}
Output:
Code Explanation:
- Using std::sort , we first sort the input string in lexicographical order.
- After that, we create and report permutations using std::next_permutation using a do-while loop . This function produces the next one until there are no more lexicographically bigger permutations to be formed.
- The current permutation that we output inside the loop will be sorted in order because of the first sorting step.
- With the input "XYZ" , this code will output the possibilities in lexicographic order when it is run.
