Escriba un programa para imprimir todas las permutaciones distintas de una string dada en orden ordenado. Tenga en cuenta que la string de entrada puede contener caracteres duplicados.
En matemáticas, la noción de permutación se relaciona con el acto de ordenar todos los miembros de un conjunto en alguna secuencia u orden, o si el conjunto ya está ordenado, reorganizar (reordenar) sus elementos, un proceso llamado permutación.
Fuente – Wikipedia
Ejemplos:
Entrada: BAC
Salida: ABC ACB BAC BCA CAB CBA
Entrada: AAB
Salida: AAB ABA BAA
Entrada: DBCA
Salida: ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
Concepto Utilizado: El número de Strings generados por una string de caracteres distintos de longitud ‘n’ es igual a ‘n!’. Ordenar cualquier string dada y generar lexicográficamente la siguiente string más grande hasta llegar a la string lexicográficamente más grande de esos caracteres.
Diferentes permutaciones de la palabra «geeks»
Longitud de la string = 5
El carácter ‘e’ se repite 2 veces.
Resultado = 5!/2! = 60.
Pasos:
Ejemplo: Considere una string «ABCD».
Paso 1: ordenar la string.
Paso 2: Obtenga el número total de permutaciones que se pueden formar a partir de esa string .
Paso 3: imprima la string ordenada y luego haga un bucle para el número de (permutaciones-1) veces que la primera string ya está impresa.
Paso 4: encuentre la siguiente string mayor, .
Aquí está la implementación de este problema:
C++
// C++ program to print all permutations
// of a string in sorted order.
#include <bits/stdc++.h>
using namespace std;
// Calculating factorial of a number
int factorial(int n)
{
int f = 1;
for (int i = 1; i <= n; i++)
f = f * i;
return f;
}
// Method to find total number of permutations
int calculateTotal(string temp, int n)
{
int f = factorial(n);
// Building Map to store frequencies of
// all characters.
map<char, int> hm;
for (int i = 0; i < temp.length(); i++)
{
hm[temp[i]]++;
}
// Traversing map and
// finding duplicate elements.
for (auto e : hm)
{
int x = e.second;
if (x > 1)
{
int temp5 = factorial(x);
f /= temp5;
}
return f;
}
}
static void nextPermutation(string &temp)
{
// Start traversing from the end and
// find position 'i-1' of the first character
// which is greater than its successor.
int i;
for (i = temp.length() - 1; i > 0; i--)
if (temp[i] > temp[i - 1]) break;
// Finding smallest character after 'i-1' and
// greater than temp[i-1]
int min = i;
int j, x = temp[i - 1];
for (j = i + 1; j < temp.length(); j++)
if ((temp[j] < temp[min]) and
(temp[j] > x))
min = j;
// Swapping the above found characters.
swap(temp[i - 1], temp[min]);
// Sort all digits from position next to 'i-1'
// to end of the string.
sort(temp.begin() + i, temp.end());
// Print the String
cout << temp << endl;
}
void printAllPermutations(string s)
{
// Sorting String
string temp(s);
sort(temp.begin(), temp.end());
// Print first permutation
cout << temp << endl;
// Finding the total permutations
int total = calculateTotal(temp, temp.length());
for (int i = 1; i < total; i++)
{
nextPermutation(temp);
}
}
// Driver Code
int main()
{
string s = "AAB";
printAllPermutations(s);
}
// This code is contributed by
// sanjeev2552
Java
// Java program to print all permutations of a string
// in sorted order.
import java.io.*;
import java.util.*;
class Solution {
// Calculating factorial of a number
static int factorial(int n) {
int f = 1;
for (int i = 1; i <= n; i++)
f = f * i;
return f;
}
// Method to print the array
static void print(char[] temp) {
for (int i = 0; i < temp.length; i++)
System.out.print(temp[i]);
System.out.println();
}
// Method to find total number of permutations
static int calculateTotal(char[] temp, int n) {
int f = factorial(n);
// Building HashMap to store frequencies of
// all characters.
HashMap<Character, Integer> hm =
new HashMap<Character, Integer>();
for (int i = 0; i < temp.length; i++) {
if (hm.containsKey(temp[i]))
hm.put(temp[i], hm.get(temp[i]) + 1);
else
hm.put(temp[i], 1);
}
// Traversing hashmap and finding duplicate elements.
for (Map.Entry e : hm.entrySet()) {
Integer x = (Integer)e.getValue();
if (x > 1) {
int temp5 = factorial(x);
f = f / temp5;
}
}
return f;
}
static void nextPermutation(char[] temp) {
// Start traversing from the end and
// find position 'i-1' of the first character
// which is greater than its successor.
int i;
for (i = temp.length - 1; i > 0; i--)
if (temp[i] > temp[i - 1])
break;
// Finding smallest character after 'i-1' and
// greater than temp[i-1]
int min = i;
int j, x = temp[i - 1];
for (j = i + 1; j < temp.length; j++)
if ((temp[j] < temp[min]) && (temp[j] > x))
min = j;
// Swapping the above found characters.
char temp_to_swap;
temp_to_swap = temp[i - 1];
temp[i - 1] = temp[min];
temp[min] = temp_to_swap;
// Sort all digits from position next to 'i-1'
// to end of the string.
Arrays.sort(temp, i, temp.length);
// Print the String
print(temp);
}
static void printAllPermutations(String s) {
// Sorting String
char temp[] = s.toCharArray();
Arrays.sort(temp);
// Print first permutation
print(temp);
// Finding the total permutations
int total = calculateTotal(temp, temp.length);
for (int i = 1; i < total; i++)
nextPermutation(temp);
}
// Driver Code
public static void main(String[] args) {
String s = "AAB";
printAllPermutations(s);
}
}
Python3
# Python3 program to print
# all permutations of a
# string in sorted order.
from collections import defaultdict
# Calculating factorial
# of a number
def factorial(n):
f = 1
for i in range (1, n + 1):
f = f * i
return f
# Method to find total
# number of permutations
def calculateTotal(temp, n):
f = factorial(n)
# Building Map to store
# frequencies of all
# characters.
hm = defaultdict (int)
for i in range (len(temp)):
hm[temp[i]] += 1
# Traversing map and
# finding duplicate elements.
for e in hm:
x = hm[e]
if (x > 1):
temp5 = factorial(x)
f //= temp5
return f
def nextPermutation(temp):
# Start traversing from
# the end and find position
# 'i-1' of the first character
# which is greater than its successor
for i in range (len(temp) - 1, 0, -1):
if (temp[i] > temp[i - 1]):
break
# Finding smallest character
# after 'i-1' and greater
# than temp[i-1]
min = i
x = temp[i - 1]
for j in range (i + 1, len(temp)):
if ((temp[j] < temp[min]) and
(temp[j] > x)):
min = j
# Swapping the above
# found characters.
temp[i - 1], temp[min] = (temp[min],
temp[i - 1])
# Sort all digits from
# position next to 'i-1'
# to end of the string
temp[i:].sort()
# Print the String
print (''.join(temp))
def printAllPermutations(s):
# Sorting String
temp = list(s)
temp.sort()
# Print first permutation
print (''.join( temp))
# Finding the total permutations
total = calculateTotal(temp,
len(temp))
for i in range (1, total):
nextPermutation(temp)
# Driver Code
if __name__ == "__main__":
s = "AAB"
printAllPermutations(s)
# This code is contributed by Chitranayal
C#
// C# program to print all permutations
// of a string in sorted order.
using System;
using System.Collections.Generic;
class GFG
{
// Calculating factorial of a number
static int factorial(int n)
{
int f = 1;
for (int i = 1; i <= n; i++)
f = f * i;
return f;
}
// Method to print the array
static void print(char[] temp)
{
for (int i = 0; i < temp.Length; i++)
Console.Write(temp[i]);
Console.WriteLine();
}
// Method to find total number of permutations
static int calculateTotal(char[] temp, int n)
{
int f = factorial(n);
// Building Dictionary to store frequencies
// of all characters.
Dictionary<char,
int> hm = new Dictionary<char,
int>();
for (int i = 0; i < temp.Length; i++)
{
if (hm.ContainsKey(temp[i]))
hm[temp[i]] = hm[temp[i]] + 1;
else
hm.Add(temp[i], 1);
}
// Traversing hashmap and
// finding duplicate elements.
foreach(KeyValuePair<char, int> e in hm)
{
int x = e.Value;
if (x > 1)
{
int temp5 = factorial(x);
f = f / temp5;
}
}
return f;
}
static void nextPermutation(char[] temp)
{
// Start traversing from the end and
// find position 'i-1' of the first character
// which is greater than its successor.
int i;
for (i = temp.Length - 1; i > 0; i--)
if (temp[i] > temp[i - 1])
break;
// Finding smallest character after 'i-1'
// and greater than temp[i-1]
int min = i;
int j, x = temp[i - 1];
for (j = i + 1; j < temp.Length; j++)
if ((temp[j] < temp[min]) && (temp[j] > x))
min = j;
// Swapping the above found characters.
char temp_to_swap;
temp_to_swap = temp[i - 1];
temp[i - 1] = temp[min];
temp[min] = temp_to_swap;
// Sort all digits from position next to 'i-1'
// to end of the string.
Array.Sort(temp, i, temp.Length-i);
// Print the String
print(temp);
}
static void printAllPermutations(String s)
{
// Sorting String
char []temp = s.ToCharArray();
Array.Sort(temp);
// Print first permutation
print(temp);
// Finding the total permutations
int total = calculateTotal(temp, temp.Length);
for (int i = 1; i < total; i++)
nextPermutation(temp);
}
// Driver Code
public static void Main(String[] args)
{
String s = "AAB";
printAllPermutations(s);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to print all permutations of a string
// in sorted order.
// Calculating factorial of a number
function factorial(n)
{
let f = 1;
for (let i = 1; i <= n; i++)
f = f * i;
return f;
}
// Method to print the array
function print(temp)
{
for (let i = 0; i < temp.length; i++)
document.write(temp[i]);
document.write("<br>");
}
// Method to find total number of permutations
function calculateTotal(temp,n)
{
let f = factorial(n);
// Building HashMap to store frequencies of
// all characters.
let hm = new Map();
for (let i = 0; i < temp.length; i++) {
if (hm.has(temp[i]))
hm.set(temp[i], hm.get(temp[i]) + 1);
else
hm.set(temp[i], 1);
}
// Traversing hashmap and finding duplicate elements.
for (let [key, value] of hm.entries()) {
let x = value;
if (x > 1) {
let temp5 = factorial(x);
f = Math.floor(f / temp5);
}
}
return f;
}
function nextPermutation(temp)
{
// Start traversing from the end and
// find position 'i-1' of the first character
// which is greater than its successor.
let i;
for (i = temp.length - 1; i > 0; i--)
if (temp[i] > temp[i - 1])
break;
// Finding smallest character after 'i-1' and
// greater than temp[i-1]
let min = i;
let j, x = temp[i - 1];
for (j = i + 1; j < temp.length; j++)
if ((temp[j] < temp[min]) && (temp[j] > x))
min = j;
// Swapping the above found characters.
let temp_to_swap;
temp_to_swap = temp[i - 1];
temp[i - 1] = temp[min];
temp[min] = temp_to_swap;
// Sort all digits from position next to 'i-1'
// to end of the string.
temp=temp.slice(0,i).sort().concat(temp.slice(i,temp.length));
// Print the String
print(temp);
}
function printAllPermutations(s)
{
// Sorting String
let temp = s.split("");
temp.sort();
// Print first permutation
print(temp);
// Finding the total permutations
let total = calculateTotal(temp, temp.length);
for (let i = 1; i < total; i++)
nextPermutation(temp);
}
// Driver Code
let s = "AAB";
printAllPermutations(s);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
AAB ABA BAA
Complejidad de tiempo: O(n*m) donde n es el tamaño de la array y m es el número de permutaciones posibles.
Espacio Auxiliar: O(n).
Publicación traducida automáticamente
Artículo escrito por akisonlyforu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA