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.

Permutations of a given string

Algorithm :

  • Sort the given string in non-decreasing order and print it.
  • The first permutation is always the string sorted in non-decreasing order.
  • Start generating next higher permutation.
  • Repeat it until next higher permutation is not possible.
  • If we reach a permutation where all characters are sorted in non-increasing order, then that permutation is the last permutation.
Permutations of a string in lexicographically sorted order in C

Code in C

Run 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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 );
 
    int isFinished = 0;
    while ( ! isFinished )
    {
        printf ("%s \n", str);
 
        int i;
        for ( i = size - 2; i >= 0; --i )
        if (str[i] < str[i+1])
            break;
 
        if ( i == -1 )
            isFinished = 1;
        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
 
 

Remove brackets from an algebraic expression

Remove spaces from a string

Remove the vowels from a String

Prime Course Trailer

Related Banners

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

Get Prime
Software Engineering SDLC

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


  • Pulivendula

    import java.util.*;
    public class Main
    {
    public static void main(String[] args)
    {
    String a=”ABC”;
    String b=””;
    pa(a,b);
    }
    public static void pa(String a , String b)
    {
    if(a.length()==0)
    {
    System.out.print(b+” “);
    return;
    }
    for(int i=0; i<a.length(); i++)
    {
    char c = a.charAt(i);
    String r = a.substring(0,i)+a.substring(i+1);
    pa(r,b+c);
    }
    }
    }