Dada una string que puede contener duplicados, escriba una función para imprimir todas las permutaciones de la string dada de modo que ninguna permutación se repita en la salida.
Ejemplos:
Input: str[] = "AB"
Output: AB BA
Input: str[] = "AA"
Output: AA
Input: str[] = "ABC"
Output: ABC ACB BAC BCA CBA CAB
Input: str[] = "ABA"
Output: ABA AAB BAA
Input: str[] = "ABCA"
Output: AABC AACB ABAC ABCA ACBA ACAB BAAC BACA
BCAA CABA CAAB CBAA
Hemos discutido un algoritmo para imprimir todas las permutaciones en la publicación a continuación. Se recomienda encarecidamente consultar la publicación a continuación como requisito previo para esta publicación.
Escriba un programa en C para imprimir todas las permutaciones de una string dada
. El algoritmo discutido en el enlace anterior no maneja duplicados.
CPP
// 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(). */
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
static int x = 1;
cout << x++ << " " << str << endl;
// printf("%d %s \n", x++, 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[] = "ACBC";
sortedPermutations(str);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// Program to print all permutations of a string in sorted
// order.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Following function is needed for library
function 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
static int x = 1;
printf("%d %s \n", x++, 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[] = "ACBC";
sortedPermutations(str);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
1 ABCC 2 ACBC 3 ACCB 4 BACC 5 BCAC 6 BCCA 7 CABC 8 CACB 9 CBAC 10 CBCA 11 CCAB 12 CCBA
El código anterior está tomado de un comentario a continuación por el Sr. Lazy.
Complejidad de Tiempo: O(n 2 * n!)
Espacio Auxiliar: O(1)
El algoritmo anterior está en la complejidad temporal de O(n2 * n!) pero podemos lograr una mejor complejidad temporal de O(n!*n) que estaba allí en el caso de todos los caracteres distintos en la entrada mediante alguna modificación en eso algoritmo. El algoritmo de caracteres distintivos se puede encontrar aquí: https://www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/
Enfoque eficiente: en nuestra función recursiva para encontrar todas las permutaciones, podemos usar unordered_set para encargarnos del elemento duplicado que queda en la string activa. Mientras iteramos sobre los elementos de la string, buscaremos ese elemento en unordered_set y, si lo encuentra, omitiremos esa iteración o, de lo contrario, insertaremos ese elemento en unordered_set. Como en promedio, todas las operaciones de unordered_set como insert() y find() están en tiempo O(1), entonces la complejidad del tiempo del algoritmo no cambiará al usar unordered_set.
La implementación del algoritmo es la siguiente:
C++
#include <bits/stdc++.h>
using namespace std;
void printAllPermutationsFast(string s, string l)
{
if (s.length() < 1)
cout << l + s << endl;
unordered_set<char> uset;
for (int i = 0; i < s.length(); i++)
{
if (uset.find(s[i]) != uset.end())
continue;
else
uset.insert(s[i]);
string temp = "";
if (i < s.length() - 1)
temp = s.substr(0, i) + s.substr(i + 1);
else
temp = s.substr(0, i);
printAllPermutationsFast(temp, l + s[i]);
}
}
int main()
{
string s = "ACBC";
sort(s.begin(), s.end());
printAllPermutationsFast(s, "");
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 code for the same approach def printAllPermutationsFast(s, l): if (len(s) < 1): print(l + s) uset = set() for i in range(len(s)): if s[i] in uset: continue else: uset.add(s[i]) temp = ""; if (i < len(s) - 1): temp = s[:i] + s[i + 1:] else: temp = s[:i] printAllPermutationsFast(temp, l + s[i]) # Driver code s = "ACBC"; s = "".join(sorted(s)) printAllPermutationsFast(s, "") # This code is contributed by phasing17
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG
{
// Method to print all the permutations
static void printAllPermutationsFast(string s, string l)
{
if (s.Length < 1)
Console.WriteLine(l + s);
// Set of the characters of the permutation
HashSet<char> uset = new HashSet<char>();
// Iterating over the string characters
for (int i = 0; i < s.Length; i++)
{
// If this permutation has already been
// created, form the next permutation
if (uset.Contains(s[i]))
continue;
else
// Otherwise, update the set
uset.Add(s[i]);
// Create the permutation that contains the ith character
// and the permutation that does not contain the ith
// character
string temp = "";
if (i < s.Length - 1)
temp = s.Substring(0, i) + s.Substring(i + 1);
else
temp = s.Substring(0, i);
printAllPermutationsFast(temp, l + s[i]);
}
}
// Driver method
public static void Main(string[] args)
{
string s = "ACBC";
// Sorting the string
// using char array
char[] arr = s.ToCharArray();
Array.Sort(arr);
s = new string(arr);
// Function call
printAllPermutationsFast(s, "");
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code for the same approach
function printAllPermutationsFast(s, l)
{
if (s.length < 1) {
document.write(l + s,"</br>");
}
let uset = new Set();
for (let i = 0; i < s.length; i++) {
if (uset.has(s[i]) == true) {
continue;
}
else {
uset.add(s[i]);
}
let temp = "";
if (i < s.length - 1) {
temp = s.substring(0, i) + s.substring(i + 1);
}
else {
temp = s.substring(0, i);
}
printAllPermutationsFast(temp, l + s[i]);
}
}
// driver code
let s = "ACBC";
s = s.split("").sort().join("");
printAllPermutationsFast(s, "");
// This code is contributed by shinjanpatra.
</script>
ABCC ACBC ACCB BACC BCAC BCCA CABC CACB CBAC CBCA CCAB CCBA
Tiempo Complejidad – O(n*n!)
Espacio Auxiliar – O(n)
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