Job Updates
Interviews
Connect
Connect & get Notified

Permutations of a Given string in lexicographically Sorted Order

Print all permutations of String in Lexicographically Sorted Order

Definition & Explanation

we need to generate all possible permutations of a given string and then sort them lexicographically. Here’s the explanation of how this can be done:

  1. Generate Permutations: We can use Python’s itertools.permutations() function to generate all permutations of the given string.
  2. Sort Permutations: After generating all permutations, we sort them lexicographically using Python’s built-in sorted() function.
  3. Print Permutations: Finally, we iterate through the sorted permutations and print each permutation.

Here’s a step-by-step explanation:

Step 1: Generate Permutations

  • Use itertools.permutations() to generate all permutations of the given string.

Step 2: Sort Permutations

  • Use sorted() to sort the generated permutations lexicographically.

Step 3: Print Permutations

  • Iterate through the sorted permutations and print each permutation.

Program Logic

  1. Import itertools.permutations: The code begins by importing the permutations function from the itertools module. This function is used to generate all possible permutations of a sequence (in this case, a string).
  2. Define lexicographic_permutations Function: The lexicographic_permutations function is defined, which takes a string s as input.
  3. Generate Permutations:
    • The permutations(s) function generates all possible permutations of the input string s.
    • The list comprehension [ ''.join(p) for p in permutations(s) ] is used to convert each permutation (which is represented as a tuple of characters) into a string by joining the characters together. This results in a list of all permutations as strings, stored in the variable perms.
  4. Sort Permutations: The sorted(perms) function sorts the list of permutations lexicographically (in alphabetical order).
  5. Print Permutations: The program then iterates through the sorted list of permutations (sorted_perms) using a for loop. For each permutation perm in sorted_perms, it prints the permutation using the print() function.
  6. Example Usage:
    • The variable input_string is assigned the value "abc".
    • The lexicographic_permutations(input_string) function is called with input_string as the argument, which generates and prints all lexicographic permutations of the string "abc".
C

Method 1 :

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

// Function to compare two strings lexicographically
int compare(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

// Function to print all lexicographic permutations in sorted order
void lexicographic_permutations(char *str) {
    int n = strlen(str);
    
    // Generate all permutations using library function qsort
    qsort(str, n, sizeof(char), compare);
    
    // Print all permutations
    do {
        printf("%s\n", str);
    } while (next_permutation(str));
}

int main() {
    char str[] = "abc";
    lexicographic_permutations(str);
    return 0;
}

Output :

C++

Method 1 :

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

// Function to print all lexicographic permutations in sorted order
void lexicographic_permutations(string str) {
    // Sort the string lexicographically
    sort(str.begin(), str.end());
    
    // Print all permutations
    do {
        cout << str << endl;
    } while (next_permutation(str.begin(), str.end()));
}

int main() {
    string str = "abc";
    lexicographic_permutations(str);
    return 0;
}

Output :

JAVA

Method 1 :

import java.util.Arrays;

public class LexicographicPermutations {
    // Function to print all lexicographic permutations in sorted order
    public static void lexicographicPermutations(char[] str) {
        Arrays.sort(str); // Sort the character array lexicographically
        
        // Print all permutations
        do {
            System.out.println(str);
        } while (nextPermutation(str));
    }

    // Function to find the next lexicographically greater permutation
    public static boolean nextPermutation(char[] arr) {
        int n = arr.length;
        int i = n - 2;

        // Find the first element from the right that is smaller than its adjacent element
        while (i >= 0 && arr[i] >= arr[i + 1])
            i--;

        if (i < 0)
            return false; // No such element found, array is in decreasing order

        // Find the smallest element from the right which is greater than arr[i]
        int j = n - 1;
        while (arr[j] <= arr[i])
            j--;

        // Swap arr[i] and arr[j]
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        // Reverse the suffix starting at arr[i+1]
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        char[] str = "abc".toCharArray();
        lexicographicPermutations(str);
    }
}

Output :

abc
acb
bac
bca
cab
cba
Python

Method 1 :

from itertools import permutations

def lexicographic_permutations(s):
    # Generate all permutations of the string
    perms = [''.join(p) for p in permutations(s)]
    
    # Sort permutations lexicographically
    sorted_perms = sorted(perms)
    
    # Print sorted permutations
    for perm in sorted_perms:
        print(perm)

# Example usage
input_string = "abc"
lexicographic_permutations(input_string)

Output :

abc
acb
bac
bca
cab
cba
View All Codes