Given string str with unique characters and a number N, the task is to find the N-th lexicographic permutation of the string using Factoradic method.
Examples:
Input: str = “abc”, N = 3
Output: bac
Explanation:
All possible permutations in sorted order: abc, acb, bac, bca, cab, cba
3rd permutation is bac
Input: str = “aba”, N = 2
Output: aba
Explanation:
All possible permutations in sorted order: aab, aba, baa
2nd permutation is aba
Approach: The idea is to use the concept of factoradic representation. The main concept of factoradic method is to calculate the sequence of a number. The following are the steps to find the N-th lexicographic permutation using factoradic method:
- Decrement N by 1 because this method considers sorted order as the 0th permutation.
- Divide N with 1 to the length of the string and each time store the remainder in a stack while updating the value of N as N/i.
- The calculated remainder in every step is the factoradic number. So, after calculating the final factoradic representation, start appending the element in the result string which is present on the position.
- Remove the element from the stack on each iteration.
- Repeat the above three steps until the stack becomes empty.
Let’s understand this method with an example. Let the string str be “abcde” and N be 11. Then:
- Initially, 1 is subtracted from N.
N = 11 - 1 N = 10
- Now, at every iteration, divide N with i where i ranges from 1 to the length and store the remainder in a stack:
divide Remainder Quotient Factoradic 10%1 0 10 0 10%2 0 5 00 5%3 2 1 200 2%4 1 0 1200 2%5 0 0 01200
- Now, append the elements into the resultant string from the stack and continuously remove the elements from the stack. Here, the Factoradic representation of the given number is 01200. Therefore:
[0]=a <- Selected [1]=b [2]=d [3]=e [4]=f result = a [0]=b [1]=c <- Selected [2]=d [3]=e result= ac [0]=b [1]=d [2]=e <-Selected result= ace [0]=b <- Selected [1]=d result= aceb [0]=d <-selected result =acebd
- Therefore, the 11th permutation of the string is “acebd”.
Below is the implementation of the above approach:
C++
// C++ program to find the N-th lexicographic// permutation of string using Factoradic method#include <bits/stdc++.h>using namespace std;// Function to calculate nth permutation of stringvoid string_permutation(long long int n, string str){ // Creating an empty stack stack<int> s; string result; // Subtracting 1 from N because the // permutations start from 0 in // Factoradic method n = n - 1; // Loop to generate the factroid // of the sequence for (int i = 1; i < str.size() + 1; i++) { s.push(n % i); n = n / i; } // Loop to generate nth permutation for (int i = 0; i < str.size(); i++) { int a = s.top(); result += str[a]; int j; // Remove 1-element in each cycle for (j = a; j < str.length(); j++) str[j] = str[j + 1]; str[j + 1] = '\0'; s.pop(); } // Final answer cout << result << endl;}// Driver codeint main(){ string str = "abcde"; long long int n = 11; string_permutation(n, str); return 0;} |
Java
// Java program to find the N-th lexicographic// permutation of String using Factoradic methodimport java.util.*;class GFG{// Function to calculate nth permutation of Stringstatic void String_permutation(int n, String str){ // Creating an empty stack Stack<Integer> s = new Stack<Integer>(); String result = ""; // Subtracting 1 from N because the // permutations start from 0 in // Factoradic method n = n - 1; // Loop to generate the factroid // of the sequence for(int i = 1; i < str.length() + 1; i++) { s.add(n % i); n = n / i; } // Loop to generate nth permutation for(int i = 0; i < str.length(); i++) { int a = s.peek(); result += str.charAt(a); int j; // Remove 1-element in each cycle for(j = a; j < str.length() - 1; j++) str = str.substring(0, j) + str.charAt(j + 1) + str.substring(j + 1); str = str.substring(0, j + 1); s.pop(); } // Final answer System.out.print(result + "\n");}// Driver codepublic static void main(String[] args){ String str = "abcde"; int n = 11; String_permutation(n, str);}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to find # the N-th lexicographic # permutation of string # using Factoradic method# Function to calculate # nth permutation of stringdef string_permutation(n, str): # Creating an empty list s = [] result = "" str = list(str) # Subtracting 1 from N # because the permutations # start from 0 in Factoradic method n = n - 1 # Loop to generate the # factroid of the sequence for i in range(1, len(str) + 1): s.append(n % i) n = int(n / i) # Loop to generate # nth permutation for i in range(len(str)): a = s[-1] result += str[a] # Remove 1-element in # each cycle for j in range(a, len(str) - 1): str[j] = str[j + 1] str[j + 1] = '\0' s.pop() # Final answer print(result)# Driver codestr = "abcde"n = 11string_permutation(n, str)# This code is contributed by avanitrachhadiya2155 |
C#
// C# program to find the N-th lexicographic// permutation of String using Factoradic methodusing System;using System.Collections.Generic;class GFG{// Function to calculate nth permutation of Stringstatic void String_permutation(int n, String str){ // Creating an empty stack Stack<int> s = new Stack<int>(); String result = ""; // Subtracting 1 from N because the // permutations start from 0 in // Factoradic method n = n - 1; // Loop to generate the factroid // of the sequence for(int i = 1; i < str.Length + 1; i++) { s.Push(n % i); n = n / i; } // Loop to generate nth permutation for(int i = 0; i < str.Length; i++) { int a = s.Peek(); result += str[a]; int j; // Remove 1-element in each cycle for(j = a; j < str.Length - 1; j++) { str = str.Substring(0, j) + str[j + 1] + str.Substring(j + 1); } str = str.Substring(0, j + 1); s.Pop(); } // Final answer Console.Write(result + "\n");}// Driver codepublic static void Main(String[] args){ String str = "abcde"; int n = 11; String_permutation(n, str);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// JavaScript program to find the N-th lexicographic// permutation of string using Factoradic method// Function to calculate nth permutation of stringfunction string_permutation( n, str){ // Creating an empty stack let s = []; let result = ''; // Subtracting 1 from N because the // permutations start from 0 in // Factoradic method n = n - 1; // Loop to generate the factroid // of the sequence for (let i = 1; i < str.length + 1; i++) { s.push(n % i); n = Math.floor(n / i); } // Loop to generate nth permutation let len = str.length; for (let i = 0; i < len ; i++) { let a = s[s.length-1]; result += str[a]; let j; // Remove 1-element in each cycle for (j = a; j < str.length ; j++) str = str.substring(0, j) + str.charAt(j + 1) + str.substring(j + 1); str = str.substring(0, j + 1); s.pop(); } // Final answer document.write(result,'<br>');}// Driver codelet str = "abcde";n = 11;string_permutation(n, str);</script> |
Output:
acebd
Time Complexity: O(|str|)
Auxiliary Space: O(|str|)
Note: An approach to find the Nth permutation with the repeating characters is discussed in this article.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
