Dada una string, imprima todas sus permutaciones en orden ordenado. Por ejemplo, si la string de entrada es «ABC», la salida debe ser «ABC, ACB, BAC, BCA, CAB, CBA».
Hemos discutido un programa para imprimir todas las permutaciones en esta publicación, pero aquí debemos imprimir las permutaciones en orden creciente.
Algoritmo para imprimir las permutaciones lexicográficamente:
Paso 1. Ordenar la string dada en orden no decreciente e imprimirla. La primera permutación es siempre la string ordenada en orden no decreciente.
Paso 2. Comience a generar la siguiente permutación más alta. Hágalo hasta que la siguiente permutación más alta no sea posible. Si llegamos a una permutación donde todos los caracteres están ordenados y en orden no creciente, entonces esa permutación es la última permutación.
Pasos para generar la siguiente permutación más alta:
Paso 1. Tome la permutación previamente impresa y encuentre el carácter más a la derecha en ella, que es más pequeño que su siguiente carácter. Llamemos a este personaje como ‘primer personaje’.
Paso 2. Ahora encuentra el techo del ‘primer carácter’. El techo es el carácter más pequeño a la derecha del ‘primer carácter’, que es mayor que el ‘primer carácter’. Llamemos al carácter ceil como ‘segundo carácter’.
Paso 3. Intercambia los dos personajes que se encuentran en los 2 pasos anteriores.
Paso 4. Ordene la substring (en orden no decreciente) después del índice original de ‘primer carácter’.
Acercarse:
1. Consideremos la string “ABCDEF”. Deje que la permutación previamente impresa sea «DCFEBA».
2. La siguiente permutación en orden debe ser «DEABCF».
3. Comprendamos los pasos anteriores para encontrar la siguiente permutación. El ‘primer carácter’ será ‘C’. El ‘segundo carácter’ será ‘E’. Después de intercambiar estos dos, obtenemos «DEFCBA».
4. El paso final es ordenar la substring después del índice original del carácter del ‘primer carácter’. Finalmente, obtenemos “DEABCF”.
A continuación se muestra la implementación del algoritmo.
C++
// C++ Program to print all permutations
// of a string in sorted order.
#include <bits/stdc++.h>
using namespace std;
/* Following function is needed for library function qsort(). Refer
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
int compare (const void *a, const void * b)
{ return ( *(char *)a - *(char *)b ); }
// A utility function two swap two characters a and b
void swap (char* a, char* b)
{
char t = *a;
*a = *b;
*b = t;
}
// This function finds the index of the smallest character
// which is greater than 'first' and is present in str[l..h]
int findCeil (char str[], char first, int l, int h)
{
// initialize index of ceiling element
int ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (int i = l+1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
// Print all permutations of str in sorted order
void sortedPermutations ( char str[] )
{
// Get size of string
int size = strlen(str);
// Sort the string in increasing order
qsort( str, size, sizeof( str[0] ), compare );
// Print permutations one by one
bool isFinished = false;
while ( ! isFinished )
{
// print this permutation
cout << str << endl;
// Find the rightmost character which is
// smaller than its next character.
// Let us call it 'first char'
int i;
for ( i = size - 2; i >= 0; --i )
if (str[i] < str[i+1])
break;
// If there is no such character, all are
// sorted in decreasing order, means we
// just printed the last permutation and we are done.
if ( i == -1 )
isFinished = true;
else
{
// Find the ceil of 'first char' in
// right of first character.
// Ceil of a character is the smallest
// character greater than it
int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );
// Swap first and second characters
swap( &str[i], &str[ceilIndex] );
// Sort the string on right of 'first char'
qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
}
}
}
// Driver program to test above function
int main()
{
char str[] = "ABCD";
sortedPermutations( str );
return 0;
}
// This is code is contributed by rathbhupendra
C
// Program to print all permutations of a string in sorted order.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Following function is needed for library function qsort(). Refer
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
int compare (const void *a, const void * b)
{ return ( *(char *)a - *(char *)b ); }
// A utility function two swap two characters a and b
void swap (char* a, char* b)
{
char t = *a;
*a = *b;
*b = t;
}
// This function finds the index of the smallest character
// which is greater than 'first' and is present in str[l..h]
int findCeil (char str[], char first, int l, int h)
{
// initialize index of ceiling element
int ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (int i = l+1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
// Print all permutations of str in sorted order
void sortedPermutations ( char str[] )
{
// Get size of string
int size = strlen(str);
// Sort the string in increasing order
qsort( str, size, sizeof( str[0] ), compare );
// Print permutations one by one
bool isFinished = false;
while ( ! isFinished )
{
// print this permutation
printf ("%s \n", str);
// Find the rightmost character which is smaller than its next
// character. Let us call it 'first char'
int i;
for ( i = size - 2; i >= 0; --i )
if (str[i] < str[i+1])
break;
// If there is no such character, all are sorted in decreasing order,
// means we just printed the last permutation and we are done.
if ( i == -1 )
isFinished = true;
else
{
// Find the ceil of 'first char' in right of first character.
// Ceil of a character is the smallest character greater than it
int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );
// Swap first and second characters
swap( &str[i], &str[ceilIndex] );
// Sort the string on right of 'first char'
qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
}
}
}
// Driver program to test above function
int main()
{
char str[] = "ABCD";
sortedPermutations( str );
return 0;
}
Java
// Java Program to print all permutations
// of a string in sorted order.
import java.util.*;
class GFG
{
// This function finds the index of the smallest
// character which is greater than 'first' and is
// present in str[l..h]
static int findCeil(char[] str, char first, int l,
int h)
{
// initialize index of ceiling element
int ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
// Print all permutations of str in sorted order
static void sortedPermutations(char[] str)
{
// Get size of string
int size = str.length;
// Sort the string in increasing order
Arrays.sort(str);
// Print permutations one by one
boolean isFinished = false;
while (!isFinished) {
// print this permutation
System.out.println(String.valueOf(str));
// Find the rightmost character which is
// smaller than its next character.
// Let us call it 'first char'
int i;
for (i = size - 2; i >= 0; --i)
if (str[i] < str[i + 1])
break;
// If there is no such character, all are
// sorted in decreasing order, means we
// just printed the last permutation and we are
// done.
if (i == -1)
isFinished = true;
else {
// Find the ceil of 'first char' in
// right of first character.
// Ceil of a character is the smallest
// character greater than it
int ceilIndex = findCeil(str, str[i], i + 1,
size - 1);
// Swap first and second characters
char temp = str[i];
str[i] = str[ceilIndex];
str[ceilIndex] = temp;
// Sort the string on right of 'first char'
Arrays.sort(str, i + 1, size);
}
}
}
// Driver program to test above function
public static void main(String[] args)
{
char[] str = { 'A', 'B', 'C', 'D' };
sortedPermutations(str);
}
}
// This is code is contributed by phasing17
Python3
# Python3 Program to print all permutations
# of a string in sorted order.
# The following function is needed for the sort method
# This function finds the index of the smallest character
# which is greater than 'first' and is present in str[l..h]
def findCeil(str_, first, l, h):
# initialize index of ceiling element
ceilIndex = l
# Now iterate through rest of the elements and find
# the smallest character greater than 'first'
for i in range(l + 1, h + 1):
if (str_[i] > first and str_[i] < str_[ceilIndex]):
ceilIndex = i
return ceilIndex
# Print all permutations of str in sorted order
def sortedPermutations(str_):
# Get size of string
size = len(str_)
# Sort the string in increasing order
str_ = sorted(str_)
# Print permutations one by one
isFinished = False
while (isFinished is False):
# print this permutation
print("".join(str_))
# Find the rightmost character which is
# smaller than its next character.
# Let us call it 'first char'
i = size - 2
while i >= 0:
if (str_[i] < str_[i+1]):
break
i -= 1
# If there is no such character, all are
# sorted in decreasing order, means we
# just printed the last permutation and we are done.
if (i == -1):
isFinished = True
else:
# Find the ceil of 'first char' in
# right of first character.
# Ceil of a character is the smallest
# character greater than it
ceilIndex = findCeil(str_, str_[i], i + 1, size - 1)
# Swap first and second characters
temp = str_[i]
str_[i] = str_[ceilIndex]
str_[ceilIndex] = temp
# Sort the string on right of 'first char'
str_ = str_[:i + 1] + sorted(str_[i + 1:])
# Driver program to test above function
str_ = "ABCD"
sortedPermutations(str_)
# This code is contributed by phasing17
C#
// C# Program to print all permutations
// of a string in sorted order.
using System;
using System.Collections.Generic;
class GFG {
// This function finds the index of the smallest
// character which is greater than 'first' and is
// present in str[l..h]
static int findCeil(char[] str, char first, int l,
int h)
{
// initialize index of ceiling element
int ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
// Print all permutations of str in sorted order
static void sortedPermutations(char[] str)
{
// Get size of string
int size = str.Length;
// Sort the string in increasing order
Array.Sort(str);
// Print permutations one by one
bool isFinished = false;
while (!isFinished) {
// print this permutation
Console.WriteLine(new string(str));
// Find the rightmost character which is
// smaller than its next character.
// Let us call it 'first char'
int i;
for (i = size - 2; i >= 0; --i)
if (str[i] < str[i + 1])
break;
// If there is no such character, all are
// sorted in decreasing order, means we
// just printed the last permutation and we are
// done.
if (i == -1)
isFinished = true;
else {
// Find the ceil of 'first char' in
// right of first character.
// Ceil of a character is the smallest
// character greater than it
int ceilIndex = findCeil(str, str[i], i + 1,
size - 1);
// Swap first and second characters
char temp = str[i];
str[i] = str[ceilIndex];
str[ceilIndex] = temp;
// Sort the string on right of 'first char'
Array.Sort(str, i + 1, size - i - 1);
}
}
}
// Driver program to test above function
public static void Main(string[] args)
{
char[] str = { 'A', 'B', 'C', 'D' };
sortedPermutations(str);
}
}
// This is code is contributed by phasing17
Javascript
// JavaScript Program to print all permutations
// of a string in sorted order.
/* The following function is needed for the sort method */
function compare (a, b)
{
return a.charCodeAt(0) - b.charCodeAt(0);
}
// This function finds the index of the smallest character
// which is greater than 'first' and is present in str[l..h]
function findCeil (str, first, l, h)
{
// initialize index of ceiling element
let ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (let i = l+1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
// Print all permutations of str in sorted order
function sortedPermutations ( str)
{
// Get size of string
let size = str.length;
// Sort the string in increasing order
str = str.split("");
str.sort(compare);
// Print permutations one by one
let isFinished = false;
while ( ! isFinished )
{
// print this permutation
console.log(str.join(""));
// Find the rightmost character which is
// smaller than its next character.
// Let us call it 'first char'
let i;
for ( i = size - 2; i >= 0; --i )
if (str[i] < str[i+1])
break;
// If there is no such character, all are
// sorted in decreasing order, means we
// just printed the last permutation and we are done.
if ( i == -1 )
isFinished = true;
else
{
// Find the ceil of 'first char' in
// right of first character.
// Ceil of a character is the smallest
// character greater than it
let ceilIndex = findCeil( str, str[i], i + 1, size - 1 );
// Swap first and second characters
let temp = str[i];
str[i] = str[ceilIndex];
str[ceilIndex] = temp;
// Sort the string on right of 'first char'
str1 = str.slice(i + 1);
str1.sort();
str = str.slice(0, i + 1);
str.push(...str1);
}
}
}
// Driver program to test above function
let str = "ABCD";
sortedPermutations( str );
// This code is contributed by phasing17
Producción:
ABCD ABDC .... .... DCAB DCBA
Complejidad del Tiempo: O(n 2 xn!)
Espacio Auxiliar: O(n)
Podemos optimizar el paso 4 del algoritmo anterior para encontrar la siguiente permutación. En lugar de ordenar el subarreglo después del ‘primer carácter’, podemos invertir el subarreglo, porque el subarreglo que obtenemos después del intercambio siempre se ordena en orden no creciente. Esta optimización hace que la complejidad del tiempo sea O(nxn!) .
Consulte el siguiente código optimizado.
C++
#include <bits/stdc++.h>
using namespace std;
// An optimized version that uses reverse instead of sort for
// finding the next permutation
// A utility function to reverse a string str[l..h]
void reverse(char str[], int l, int h)
{
while (l < h)
{
swap(&str[l], &str[h]);
l++;
h--;
}
}
// Print all permutations of str in sorted order
void sortedPermutations ( char str[] )
{
// Get size of string
int size = strlen(str);
// Sort the string in increasing order
qsort( str, size, sizeof( str[0] ), compare );
// Print permutations one by one
bool isFinished = false;
while ( ! isFinished )
{
// print this permutation
cout << str << endl;
// Find the rightmost character which
// is smaller than its next character.
// Let us call it 'first char'
int i;
for ( i = size - 2; i >= 0; --i )
if (str[i] < str[i+1])
break;
// If there is no such character, all
// are sorted in decreasing order,
// means we just printed the last
// permutation and we are done.
if ( i == -1 )
isFinished = true;
else
{
// Find the ceil of 'first char' in
// right of first character.
// Ceil of a character is the
// smallest character greater than it
int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );
// Swap first and second characters
swap( &str[i], &str[ceilIndex] );
// reverse the string on right of 'first char'
reverse( str, i + 1, size - 1 );
}
}
}
// This code is contributed by rathbhupendra
C
// An optimized version that uses reverse instead of sort for
// finding the next permutation
// A utility function to reverse a string str[l..h]
void reverse(char str[], int l, int h)
{
while (l < h)
{
swap(&str[l], &str[h]);
l++;
h--;
}
}
// Print all permutations of str in sorted order
void sortedPermutations ( char str[] )
{
// Get size of string
int size = strlen(str);
// Sort the string in increasing order
qsort( str, size, sizeof( str[0] ), compare );
// Print permutations one by one
bool isFinished = false;
while ( ! isFinished )
{
// print this permutation
printf ("%s \n", str);
// Find the rightmost character which is smaller than its next
// character. Let us call it 'first char'
int i;
for ( i = size - 2; i >= 0; --i )
if (str[i] < str[i+1])
break;
// If there is no such character, all are sorted in decreasing order,
// means we just printed the last permutation and we are done.
if ( i == -1 )
isFinished = true;
else
{
// Find the ceil of 'first char' in right of first character.
// Ceil of a character is the smallest character greater than it
int ceilIndex = findCeil( str, str[i], i + 1, size - 1 );
// Swap first and second characters
swap( &str[i], &str[ceilIndex] );
// reverse the string on right of 'first char'
reverse( str, i + 1, size - 1 );
}
}
}
Java
import java.util.*;
// An optimized version that uses reverse instead of sort
// for finding the next permutation
class GFG
{
// A utility function two swap two characters a and b
static void swap(char[] str, int i, int j)
{
char t = str[i];
str[i] = str[j];
str[j] = t;
}
// A utility function to reverse a string str[l..h]
static void reverse(char str[], int l, int h)
{
while (l < h) {
swap(str, l, h);
l++;
h--;
}
}
// This function finds the index of the smallest
// character which is greater than 'first' and is
// present in str[l..h]
static int findCeil(char str[], char first, int l,
int h)
{
// initialize index of ceiling element
int ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
// Print all permutations of str in sorted order
static void sortedPermutations(char str[])
{
// Get size of string
int size = str.length;
// Sort the string in increasing order
Arrays.sort(str);
// Print permutations one by one
boolean isFinished = false;
while (!isFinished) {
// print this permutation
System.out.println(str);
// Find the rightmost character which is
// smaller than its next character.
// Let us call it 'first char'
int i;
for (i = size - 2; i >= 0; --i)
if (str[i] < str[i + 1])
break;
// If there is no such character, all are
// sorted in decreasing order, means we
// just printed the last permutation and we are
// done.
if (i == -1)
isFinished = true;
else {
// Find the ceil of 'first char' in
// right of first character.
// Ceil of a character is the smallest
// character greater than it
int ceilIndex = findCeil(str, str[i], i + 1,
size - 1);
// Swap first and second characters
swap(str, i, ceilIndex);
// reverse the string on right of 'first
// char'
reverse(str, i + 1, size - 1);
}
}
}
// Driver program to test above function
public static void main(String[] args)
{
char str[] = "ABCD".toCharArray();
sortedPermutations(str);
}
}
// This code is contributed by Swarn Pallav Bhaskar
Python3
# An optimized version that uses reverse # instead of sort for finding the next # permutation # A utility function to reverse a # string str[l..h] def reverse(str, l, h): while (l < h) : str[l], str[h] = str[h], str[l] l += 1 h -= 1 return str def findCeil(str, c, k, n): ans = -1 val = c for i in range(k, n + 1): if str[i] > c and str[i] < val: val = str[i] ans = i return ans # Print all permutations of str in sorted order def sortedPermutations(str): # Get size of string size = len(str) # Sort the string in increasing order str = ''.join(sorted(str)) # Print permutations one by one isFinished = False while (not isFinished): # Print this permutation print(str) # Find the rightmost character which # is smaller than its next character. # Let us call it 'first char' for i in range(size - 2, -1, -1): if (str[i] < str[i + 1]): break # If there is no such character, all # are sorted in decreasing order, # means we just printed the last # permutation and we are done. if (i == -1): isFinished = True else: # Find the ceil of 'first char' in # right of first character. # Ceil of a character is the # smallest character greater than it ceilIndex = findCeil(str, str[i], i + 1, size - 1) # Swap first and second characters str[i], str[ceilIndex] = str[ceilIndex], str[i] # Reverse the string on right of 'first char' str = reverse(str, i + 1, size - 1) # This code is contributed by rohan07
C#
using System;
// An optimized version that uses reverse instead of sort
// for finding the next permutation
public class GFG {
// A utility function two swap two characters a and b
static void swap(char[] str, int i, int j) {
char t = str[i];
str[i] = str[j];
str[j] = t;
}
// A utility function to reverse a string str[l..h]
static void reverse(char []str, int l, int h) {
while (l < h) {
swap(str, l, h);
l++;
h--;
}
}
// This function finds the index of the smallest
// character which is greater than 'first' and is
// present in str[l..h]
static int findCeil(char []str, char first, int l, int h) {
// initialize index of ceiling element
int ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (int i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
// Print all permutations of str in sorted order
static void sortedPermutations(char []str) {
// Get size of string
int size = str.Length;
// Sort the string in increasing order
Array.Sort(str);
// Print permutations one by one
bool isFinished = false;
while (!isFinished) {
// print this permutation
Console.WriteLine(str);
// Find the rightmost character which is
// smaller than its next character.
// Let us call it 'first char'
int i;
for (i = size - 2; i >= 0; --i)
if (str[i] < str[i + 1])
break;
// If there is no such character, all are
// sorted in decreasing order, means we
// just printed the last permutation and we are
// done.
if (i == -1)
isFinished = true;
else {
// Find the ceil of 'first char' in
// right of first character.
// Ceil of a character is the smallest
// character greater than it
int ceilIndex = findCeil(str, str[i], i + 1, size - 1);
// Swap first and second characters
swap(str, i, ceilIndex);
// reverse the string on right of 'first
// char'
reverse(str, i + 1, size - 1);
}
}
}
// Driver program to test above function
public static void Main(String[] args) {
char []str = "ABCD".ToCharArray();
sortedPermutations(str);
}
}
// This code contributed by umadevi9616
Javascript
<script>
// An optimized version that uses reverse instead of sort
// for finding the next permutation
// A utility function two swap two characters a and b
function swap( str , i , j) {
var t = str[i];
str[i] = str[j];
str[j] = t;
}
// A utility function to reverse a string str[l..h]
function reverse( str , l , h) {
while (l < h) {
swap(str, l, h);
l++;
h--;
}
}
// This function finds the index of the smallest
// character which is greater than 'first' and is
// present in str[l..h]
function findCeil( str, first , l , h) {
// initialize index of ceiling element
var ceilIndex = l;
// Now iterate through rest of the elements and find
// the smallest character greater than 'first'
for (i = l + 1; i <= h; i++)
if (str[i] > first && str[i] < str[ceilIndex])
ceilIndex = i;
return ceilIndex;
}
// Print all permutations of str in sorted order
function sortedPermutations(str) {
// Get size of string
var size = str.length;
// Sort the string in increasing order
str.sort();
// Print permutations one by one
var isFinished = false;
while (!isFinished) {
// print this permutation
var st = str.join("");
document.write(st+"</br>");
// Find the rightmost character which is
// smaller than its next character.
// Let us call it 'first char'
var i;
for (i = size - 2; i >= 0; --i)
if (str[i] < str[i + 1])
break;
// If there is no such character, all are
// sorted in decreasing order, means we
// just printed the last permutation and we are
// done.
if (i == -1)
isFinished = true;
else {
// Find the ceil of 'first char' in
// right of first character.
// Ceil of a character is the smallest
// character greater than it
var ceilIndex = findCeil(str, str[i], i + 1, size - 1);
// Swap first and second characters
swap(str, i, ceilIndex);
// reverse the string on right of 'first
// char'
reverse(str, i + 1, size - 1);
}
}
}
// Driver program to test above function
var str = "ABCD";
str = str.split("");
sortedPermutations(str);
// This code is contributed by umadevi9616
</script>
Complejidad del tiempo: O(n*n!)
Espacio Auxiliar: O(n)
Los programas anteriores imprimen permutaciones duplicadas cuando se repiten los caracteres. Podemos evitarlo haciendo un seguimiento de la permutación anterior. Durante la impresión, si la permutación actual es la misma que la permutación anterior, no la imprimiremos.
Este artículo fue compilado por Aashish Barnwal y revisado por el equipo de GeeksforGeeks. 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