Dada una palabra, encuentre una permutación lexicográficamente más pequeña de ella. Por ejemplo, la permutación lexicográficamente más pequeña de «4321» es «4312» y la siguiente permutación más pequeña de «4312» es «4231». Si la string se ordena en orden ascendente, la siguiente permutación lexicográficamente más pequeña no existe.
Hemos discutido next_permutation() que modifica una string para que almacene permutaciones lexicográficamente más pequeñas. STL también proporciona std::prev_permutation. Devuelve ‘verdadero’ si la función puede reorganizar el objeto como una permutación lexicográficamente más pequeña. De lo contrario, devuelve ‘falso’.
C++
// C++ program to demonstrate working of
// prev_permutation()
#include <bits/stdc++.h>
using namespace std;
// Driver code
int main()
{
string str = "4321";
if (prev_permutation(str.begin(), str.end()))
cout << "Previous permutation is " << str;
else
cout << "Previous permutation doesn't exist";
return 0;
}
Producción
Previous permutation is 4312
¿Cómo escribir nuestro propio prev_permutation()?
A continuación se muestran los pasos para encontrar la permutación anterior:
- Encuentre el mayor índice i tal que str[i – 1] > str[i].
- Encuentre el mayor índice j tal que j >= i y str[j] < str[i – 1].
- Intercambiar str[j] y str[i – 1].
- Invierta el subarreglo que comienza en str[i].
A continuación se muestra la implementación de los pasos anteriores de la siguiente manera:
C++
// C++ program to print all permutations with
// duplicates allowed using prev_permutation()
#include <bits/stdc++.h>
using namespace std;
// Function to compute the previous permutation
bool prevPermutation(string& str)
{
// Find index of the last element of the string
int n = str.length() - 1;
// Find largest index i such that str[i - 1] >
// str[i]
int i = n;
while (i > 0 && str[i - 1] <= str[i])
i--;
// if string is sorted in ascending order
// we're at the last permutation
if (i <= 0)
return false;
// Note - str[i..n] is sorted in ascending order
// Find rightmost element's index that is less
// than str[i - 1]
int j = i - 1;
while (j + 1 <= n && str[j + 1] < str[i - 1])
j++;
// Swap character at i-1 with j
swap(str[i - 1], str[j]);
// Reverse the substring [i..n]
reverse(str.begin() + i, str.end());
return true;
}
// Driver code
int main()
{
string str = "4321";
if (prevPermutation(str))
cout << "Previous permutation is " << str;
else
cout << "Previous permutation doesn't exist";
return 0;
}
Java
// Java program to print all
// permutations with duplicates
// allowed using prev_permutation()
class GFG {
// Function to compute
// the previous permutation
static boolean prevPermutation(char[] str)
{
// Find index of the last
// element of the string
int n = str.length - 1;
// Find largest index i such
// that str[i - 1] > str[i]
int i = n;
while (i > 0 && str[i - 1] <= str[i]) {
i--;
}
// if string is sorted in
// ascending order we're
// at the last permutation
if (i <= 0) {
return false;
}
// Note - str[i..n] is sorted
// in ascending order Find
// rightmost element's index
// that is less than str[i - 1]
int j = i - 1;
while (j + 1 <= n && str[j + 1] <= str[i - 1]) {
j++;
}
// Swap character at i-1 with j
swap(str, i - 1, j);
// Reverse the substring [i..n]
StringBuilder sb
= new StringBuilder(String.valueOf(str));
sb.reverse();
str = sb.toString().toCharArray();
return true;
}
static String swap(char[] ch, int i, int j)
{
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.valueOf(ch);
}
// Driver code
public static void main(String[] args)
{
char[] str = "4321".toCharArray();
if (prevPermutation(str)) {
System.out.println("Previous permutation is "
+ String.valueOf(str));
}
else {
System.out.println("Previous permutation"
+ "doesn't exist");
}
}
}
// This code is contributed by 29AjayKumar
Python
# Python 3 program to
# print all permutations with
# duplicates allowed
# using prev_permutation()
# Function to compute the
# previous permutation
def prevPermutation(str):
# Find index of the last element
# of the string
n = len(str) - 1
# Find largest index i such that
# str[i - 1] > str[i]
i = n
while (i > 0 and str[i - 1] <= str[i]):
i -= 1
# if string is sorted in ascending order
# we're at the last permutation
if (i <= 0):
return False, str
# Note - str[i..n] is sorted in
# ascending order
# Find rightmost element's index
# that is less than str[i - 1]
j = i - 1
while (j + 1 <= n and
str[j + 1] < str[i - 1]):
j += 1
# Swap character at i-1 with j
str = list(str)
temp = str[i - 1]
str[i - 1] = str[j]
str[j] = temp
str = ''.join(str)
# Reverse the substring [i..n]
str[i::-1]
return True, str
# Driver code
if __name__ == '__main__':
str = "133"
b, str = prevPermutation(str)
if (b == True):
print("Previous permutation is", str)
else:
print("Previous permutation doesn't exist")
# This code is contributed by
# Sanjit_Prasad
C#
// C# program to print all
// permutations with duplicates
// allowed using prev_permutation()
using System;
class GFG {
// Function to compute
// the previous permutation
static Boolean prevPermutation(char[] str)
{
// Find index of the last
// element of the string
int n = str.Length - 1;
// Find largest index i such
// that str[i - 1] > str[i]
int i = n;
while (i > 0 && str[i - 1] <= str[i]) {
i--;
}
// if string is sorted in
// ascending order we're
// at the last permutation
if (i <= 0) {
return false;
}
// Note - str[i..n] is sorted
// in ascending order Find
// rightmost element's index
// that is less than str[i - 1]
int j = i - 1;
while (j + 1 <= n && str[j + 1] <= str[i - 1]) {
j++;
}
// Swap character at i-1 with j
swap(str, i - 1, j);
// Reverse the substring [i..n]
String sb = String.Join("", str);
sb = reverse(sb);
str = sb.ToString().ToCharArray();
return true;
}
static String swap(char[] ch, int i, int j)
{
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.Join("", ch);
}
static String reverse(String input)
{
char[] temparray = input.ToCharArray();
int left, right = 0;
right = temparray.Length - 1;
for (left = 0; left < right; left++, right--) {
// Swap values of left and right
char temp = temparray[left];
temparray[left] = temparray[right];
temparray[right] = temp;
}
return String.Join("", temparray);
}
// Driver code
public static void Main(String[] args)
{
char[] str = "4321".ToCharArray();
if (prevPermutation(str)) {
Console.WriteLine("Previous permutation is "
+ String.Join("", str));
}
else {
Console.WriteLine("Previous permutation"
+ "doesn't exist");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
// Javascript program to print all
// permutations with duplicates
// allowed using prev_permutation()
// Function to compute
// the previous permutation
function prevPermutation(str){
// Find index of the last
// element of the string
let n = str.length - 1;
// Find largest index i such
// that str[i - 1] > str[i]
let i = n;
while (i > 0 && str[i - 1] <= str[i]){
i--;
}
// If string is sorted in
// ascending order we're
// at the last permutation
if (i <= 0){
return false;
}
// Note - str[i..n] is sorted
// in ascending order Find
// rightmost element's index
// that is less than str[i - 1]
let j = i - 1;
while (j + 1 <= n && str[j + 1] < str[i - 1]){
j++;
}
// Swap character at i-1 with j
const temper = str[i - 1];
str[i - 1] = str[j];
str[j] = temper;
// Reverse the substring [i..n]
let size = n-i+1;
for (let idx = 0; idx < Math.floor(size / 2); idx++) {
let temp = str[idx + i];
str[idx + i] = str[n - idx];
str[n - idx] = temp;
}
return true;
}
// Driver code
let str = "4321".split("");
if (prevPermutation(str))
{
console.log("Previous permutation is " +
(str).join(""));
}
else
{
console.log("Previous permutation" +
"doesn't exist");
}
// This code is contributed by Gautam goel (gautamgoel962)
Producción
Previous permutation is 4312
Complejidad de Tiempo: O(n), Espacio Auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA