Dada la string str con caracteres únicos y un número N , la tarea es encontrar la N-ésima permutación lexicográfica de la string utilizando el método factorádico.
Ejemplos:
Entrada: str = “abc”, N = 3
Salida: bac
Explicación:
Todas las permutaciones posibles en orden: abc, acb, bac, bca, cab, cba La
tercera permutación es bac
Entrada: str = “aba”, N = 2
Salida : aba
Explicación:
Todas las permutaciones posibles en orden ordenado: aab, aba, baa La
segunda permutación es aba
Planteamiento: La idea es utilizar el concepto de representación factorádica. El concepto principal del método factorádico es calcular la secuencia de un número. Los siguientes son los pasos para encontrar la N-ésima permutación lexicográfica utilizando el método factorádico:
- Disminuya N en 1 porque este método considera el orden ordenado como la permutación 0.
- Divida N con 1 a la longitud de la string y almacene cada vez el resto en una pila mientras actualiza el valor de N como N/i .
- El resto calculado en cada paso es el número factorádico. Entonces, después de calcular la representación factorádica final, comience a agregar el elemento en la string de resultados que está presente en la posición.
- Retire el elemento de la pila en cada iteración.
- Repita los tres pasos anteriores hasta que la pila se vacíe.
Entendamos este método con un ejemplo. Sea la string str «abcde» y N sea 11 . Después:
- Inicialmente, se resta 1 de N.
N = 11 - 1 N = 10
- Ahora, en cada iteración, divida N con i donde i varía de 1 a la longitud y almacene el resto en una pila:
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
- Ahora, agregue los elementos a la string resultante de la pila y elimine continuamente los elementos de la pila. Aquí, la representación factorádica del número dado es 01200. Por lo tanto:
[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
- Por lo tanto, la permutación 11 de la string es «acebd» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the N-th lexicographic
// permutation of string using Factroid method
#include <bits/stdc++.h>
using namespace std;
// Function to calculate nth permutation of string
void 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
// factroid 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 code
int 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 Factroid method
import java.util.*;
class GFG{
// Function to calculate nth permutation of String
static 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
// factroid 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 code
public 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 Factroid method # Function to calculate # nth permutation of string def string_permutation(n, str): # Creating an empty list s = [] result = "" str = list(str) # Subtracting 1 from N # because the permutations # start from 0 in factroid 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 code str = "abcde" n = 11 string_permutation(n, str) # This code is contributed by avanitrachhadiya2155
C#
// C# program to find the N-th lexicographic
// permutation of String using Factroid method
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate nth permutation of String
static 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
// factroid 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 code
public 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 Factroid method
// Function to calculate nth permutation of string
function string_permutation( n, str){
// Creating an empty stack
let s = [];
let result = '';
// Subtracting 1 from N because the
// permutations start from 0 in
// factroid 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 code
let str = "abcde";
n = 11;
string_permutation(n, str);
</script>
Producción:
acebd
Complejidad de tiempo: O(|str|)
Espacio auxiliar: O(|str|)
Nota: En este artículo se analiza un enfoque para encontrar la N -ésima permutación con los caracteres repetidos .
Publicación traducida automáticamente
Artículo escrito por siddhanthapliyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA