Given a string S, task is to print all permutations of a given string in lexicographically sorted order in C++

October 14, 2022

Permutations of a given string in lexicographically sorted order in C++

Here, in this page we will discuss the program to print all permutations of a given string in lexicographically sorted order in C++ Programming language. We are given with string and need to print them.

Permutation in C++

Algorithm :

  • Sort and print the given string in ascending order.
  • The string sorted in non-decreasing order is always the first permutation.
  • Begin creating the next higher permutation.
  • Continue until the next higher permutation is no longer conceivable.
  • When we arrive at a permutation in which all characters are arranged in non-increasing order, we have arrived at the final permutation.
Permutations of a string in lexicographically sorted order in C++

Code in C++

Run 
#include <bits/stdc++.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 findCeil (char str[], char first, int l, int h)
{
    int ceilIndex = l;
 
    for (int i = l+1; i <= h; i++)
    if (str[i] > first && str[i] < str[ceilIndex])
            ceilIndex = i;
 
    return ceilIndex;
}

void sortedPermutations ( char str[] )
{
    int size = strlen(str);
 
    qsort( str, size, sizeof( str[0] ), compare );
 
    bool isFinished = false;
    while ( ! isFinished )
    {
        cout << str << endl;
        int i;
        
        for ( i = size - 2; i >= 0; --i )
        if (str[i] < str[i+1])
            break;
 
        if ( i == -1 )
            isFinished = true;
        else
        {
            int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );
            swap( &str[i], &str[ceilIndex] );
            qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
        }
    }
}

int main()
{
    char str[] = "ABC";
    sortedPermutations( str );
    return 0;
}

Output :

ABC 
ACB 
BAC 
BCA 
CAB 
CBA
 
 

Toggle each character in a string

Find the ASCII value of a character

Length of the string without using strlen() function

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime
While loop in C

5 comments on “Given a string S, task is to print all permutations of a given string in lexicographically sorted order in C++”


  • NAZIA KHAN

    java code-
    /******************************************************************************

    Online Java Compiler.
    Code, Compile, Run and Debug java program online.
    Write your code in this editor and press “Run” button to execute it.

    *******************************************************************************/

    public class Main
    {
    public static void main(String[] args) {
    String s=”ABC”;
    permutation(s,0,s.length()-1);
    }
    public static void permutation(String s,int l,int r){
    if(l==r) System.out.println(s);
    else{
    for(int i=l;i<=r;i++){
    s=swap(s,l,i);
    permutation(s,l+1,r);
    s=swap(s,l,i);
    }
    }
    }
    public static String swap(String a,int l,int i){
    char[] c=a.toCharArray();
    char temp=c[l];
    c[l]=c[i];
    c[i]=temp;
    return String.valueOf(c);
    }

    }

    0

  • msaivaishnavi2001

    #include
    #include
    using namespace std;

    void swap(int x, int y){
    int temp;
    temp = x;
    x=y;
    y=temp;
    }

    void permute(string str,int s, int e){
    if(s==e){
    cout << str << " ";
    return;
    }
    else{
    for(int i=s; i> str;
    int s=0;
    int e=str.length();
    sort(str.begin(),str.end());
    permute(str,s,e-1);
    cout << endl;
    // your code goes here
    return 0;
    }

    0