Imprime todas las permutaciones distintas de una string que tiene duplicados.
Ejemplos:
Input : ABCA Output : AABC AACB ABAC ABCA ACBA ACAB BAAC BACA BCAA CABA CAAB CBAA
Ya se ha discutido aquí un algoritmo para imprimir todas las permutaciones distintas . Aquí discutiremos un enfoque más para hacer lo mismo. Recuerde primero cómo imprimimos permutaciones sin ningún duplicado en la string de entrada. Se da aquí . Tomemos ahora el caso de la string «ABAC». Al generar permutaciones, digamos que estamos en el índice = 0, intercámbielo con todos los elementos posteriores. Cuando llegamos a i=2, vemos que en la string s[index…i-1], había un índice que es igual a s[i]. Por lo tanto, intercambiarlo producirá permutaciones repetidas. Por lo tanto, no lo intercambiamos. Lo de abajo lo explica mejor.
Ilustración : Entendamos con el siguiente ejemplo.
i = 0 1 2 3 A B A C index = 0, s[0] = A Start swapping s[index] with s[i] following it: i = index + 1 = 1 Since s[index] != s[i], swap and recur. i = 2, s[index] == s[i], don't swap i = 3, s[index] != s[i], swap and recur.
El siguiente código hace lo mismo.
C++
// C++ program to distinct permutations of the string #include <bits/stdc++.h> using namespace std; // Returns true if str[curr] does not matches with any of the // characters after str[start] bool shouldSwap(char str[], int start, int curr) { for (int i = start; i < curr; i++) if (str[i] == str[curr]) return 0; return 1; } // Prints all distinct permutations in str[0..n-1] void findPermutations(char str[], int index, int n) { if (index >= n) { cout << str << endl; return; } for (int i = index; i < n; i++) { // Proceed further for str[i] only if it // doesn't match with any of the characters // after str[index] bool check = shouldSwap(str, index, i); if (check) { swap(str[index], str[i]); findPermutations(str, index + 1, n); swap(str[index], str[i]); } } } // Driver code int main() { char str[] = "ABCA"; int n = strlen(str); findPermutations(str, 0, n); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to distinct permutations of the string #include <stdbool.h> #include <stdio.h> #include <string.h> // Returns true if str[curr] does not matches with any of // the characters after str[start] bool shouldSwap(char str[], int start, int curr) { for (int i = start; i < curr; i++) if (str[i] == str[curr]) return 0; return 1; } // Prints all distinct permutations in str[0..n-1] void findPermutations(char str[], int index, int n) { if (index >= n) { printf("%s\n", str); return; } for (int i = index; i < n; i++) { // Proceed further for str[i] only if it // doesn't match with any of the characters // after str[index] bool check = shouldSwap(str, index, i); if (check) { // Swapping the str[index] with str[i] char temp = str[index]; str[index] = str[i]; str[i] = temp; findPermutations(str, index + 1, n); // Swapping the str[index] with str[i] temp = str[index]; str[index] = str[i]; str[i] = temp; } } } // Driver code int main() { char str[] = "ABCA"; int n = strlen(str); findPermutations(str, 0, n); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to distinct permutations of the string public class GFG { // Returns true if str[curr] does not matches with any of the // characters after str[start] static boolean shouldSwap(char str[], int start, int curr) { for (int i = start; i < curr; i++) { if (str[i] == str[curr]) { return false; } } return true; } // Prints all distinct permutations in str[0..n-1] static void findPermutations(char str[], int index, int n) { if (index >= n) { System.out.println(str); return; } for (int i = index; i < n; i++) { // Proceed further for str[i] only if it // doesn't match with any of the characters // after str[index] boolean check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1, n); swap(str, index, i); } } } static void swap(char[] str, int i, int j) { char c = str[i]; str[i] = str[j]; str[j] = c; } // Driver code public static void main(String[] args) { char str[] = {'A', 'B', 'C', 'A'}; int n = str.length; findPermutations(str, 0, n); } }
Python3
# Python3 program to distinct # permutations of the string # Returns true if str[curr] does not # matches with any of the characters # after str[start] def shouldSwap(string, start, curr): for i in range(start, curr): if string[i] == string[curr]: return 0 return 1 # Prints all distinct permutations # in str[0..n-1] def findPermutations(string, index, n): if index >= n: print(''.join(string)) return for i in range(index, n): # Proceed further for str[i] only # if it doesn't match with any of # the characters after str[index] check = shouldSwap(string, index, i) if check: string[index], string[i] = string[i], string[index] findPermutations(string, index + 1, n) string[index], string[i] = string[i], string[index] # Driver code if __name__ == "__main__": string = list("ABCA") n = len(string) findPermutations(string, 0, n) # This code is contributed by Rituraj Jain
C#
// C# program to distinct permutations // of the string using System; class GFG { // Returns true if str[curr] does // not matches with any of the // characters after str[start] static bool shouldSwap(char []str, int start, int curr) { for (int i = start; i < curr; i++) { if (str[i] == str[curr]) { return false; } } return true; } // Prints all distinct permutations // in str[0..n-1] static void findPermutations(char []str, int index, int n) { if (index >= n) { Console.WriteLine(str); return; } for (int i = index; i < n; i++) { // Proceed further for str[i] only // if it doesn't match with any of // the characters after str[index] bool check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1, n); swap(str, index, i); } } } static void swap(char[] str, int i, int j) { char c = str[i]; str[i] = str[j]; str[j] = c; } // Driver code public static void Main() { char []str = {'A', 'B', 'C', 'A'}; int n = str.Length; findPermutations(str, 0, n); } } // This code is contributed // by 29AjayKumar
Javascript
<script> // Javascript program to distinct permutations of the string // Returns true if str[curr] does not matches with any of the // characters after str[start] function shouldSwap(str, start, curr) { for (let i = start; i < curr; i++) { if (str[i] == str[curr]) { return false; } } return true; } // Prints all distinct permutations in str[0..n-1] function findPermutations(str, index, n) { if (index >= n) { document.write(str); document.write("<br/>") return; } for (let i = index; i < n; i++) { // Proceed further for str[i] only if it // doesn't match with any of the characters // after str[index] let check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1, n); swap(str, index, i); } } } function swap(str, i, j) { let c = str[i]; str[i] = str[j]; str[j] = c; } // Driver code let str = ['A', 'B', 'C', 'A']; let n = str.length; findPermutations(str, 0, n); </script>
ABCA ABAC ACBA ACAB AACB AABC BACA BAAC BCAA CBAA CABA CAAB
Mejor enfoque:
Generar todas las strings distintas es simplemente usar algunas condiciones if. La técnica anterior utiliza un bucle adicional dentro de la recursividad que provoca un mayor costo de complejidad de tiempo. En cambio, podemos mejorarlo con un pequeño procesamiento previo. Primero ordenamos la string dada y luego aplicamos el siguiente código.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to print all the permutation // of the given string. #include <algorithm> #include <iostream> #include <string> using namespace std; // count of total permutations int total = 0; void permute(int i, string s) { // base case if (i == (s.length() - 1)) { cout << s << endl; total++; return; } char prev = '*'; // loop from j = 1 to length of string for (int j = i; j < s.length(); j++) { string temp = s; if (j > i && temp[i] == temp[j]) continue; if (prev != '*' && prev == s[j]) { continue; } // swap the elements swap(temp[i], temp[j]); prev = s[j]; // recursion call permute(i + 1, temp); } } // Driver code int main() { string s = "abca"; // sort sort(s.begin(), s.end()); // Function call permute(0, s); cout << "Total distinct permutations = " << total << endl; return 0; } // This code is contributed by risingStark.
Java
// Java program to print all the permutation // of the given String. //include <algorithm> //include <String> import java.util.*; class GFG{ // Count of total permutations static int total = 0; static void permute(int i, String s) { // Base case if (i == (s.length() - 1)) { System.out.print(s + "\n"); total++; return; } char prev = '*'; // Loop from j = 1 to length of String for(int j = i; j < s.length(); j++) { char []temp = s.toCharArray(); if (j > i && temp[i] == temp[j]) continue; if (prev != '*' && prev == s.charAt(j)) { continue; } // Swap the elements temp = swap(temp,i,j); prev = s.charAt(j); // Recursion call permute(i + 1, String.valueOf(temp)); } } static char[] swap(char []arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } static String sortString(String inputString) { // Convert input string to char array char tempArray[] = inputString.toCharArray(); // Sort tempArray Arrays.sort(tempArray); // Return new sorted string return new String(tempArray); } // Driver code public static void main(String[] args) { String s = "abca"; // Sort s = sortString(s); // Function call permute(0, s); System.out.print("Total distinct permutations = " + total +"\n"); } } // This code is contributed by Amit Katiyar
Python3
# Python program to print all the permutation # of the given String. # Count of total permutations total = 0 def swap(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp return arr def permute(i, s): global total # Base case if(i == (len(s) - 1)): print(s) total += 1 return prev = '*' # Loop from j = 1 to length of String for j in range(i,len(s)): temp = list(s) if (j > i and temp[i] == temp[j]): continue if (prev != '*' and prev == s[j]): continue # Swap the elements temp = swap(temp,i,j) prev = s[j] # Recursion call permute(i + 1, "".join(temp)) def sortString(inputString): # Convert input string to char array tempArray = list(inputString) # Sort tempArray tempArray.sort() # Return new sorted string return "".join(tempArray) # Driver code s = "abca" # Sort s = sortString(s) # Function call permute(0, s) print(f"Total distinct permutations = {total}") # This code is contributed by shinjanpatra
C#
// C# program to print all the permutation // of the given String. using System; using System.Collections.Generic; class GFG { // Count of total permutations static int total = 0; static void permute(int i, string s) { // Base case if (i == (s.Length - 1)) { Console.Write(Convert.ToString(s) + "\n"); total++; return; } char prev = '*'; // Loop from j = 1 to length of String for (int j = i; j < s.Length; j++) { char[] temp = s.ToCharArray(); if (j > i && temp[i] == temp[j]) continue; if (prev != '*' && prev == s[j]) { continue; } // Swap the elements temp = swap(temp, i, j); prev = s[j]; // Recursion call permute(i + 1, new string(temp)); } } static char[] swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } static string sortString(string inputString) { // Convert input string to char array char[] tempArray = inputString.ToCharArray(); // Sort tempArray Array.Sort(tempArray); // Return new sorted string return new string(tempArray); } // Driver code public static void Main(string[] args) { string s = "abca"; // Sort s = sortString(s); // Function call permute(0, s); Console.Write("Total distinct permutations = " + total + "\n"); } } // This code is contributed by phasing17
Javascript
<script> // JavaScript program to print all the permutation // of the given String. // Count of total permutations let total = 0; function permute(i,s) { // Base case if (i == (s.length - 1)) { document.write(s + "<br>"); total++; return; } let prev = '*'; // Loop from j = 1 to length of String for(let j = i; j < s.length; j++) { let temp = s.split(""); if (j > i && temp[i] == temp[j]) continue; if (prev != '*' && prev == s[j]) { continue; } // Swap the elements temp = swap(temp,i,j); prev = s[j]; // Recursion call permute(i + 1, (temp).join("")); } } function swap(arr,i,j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } function sortString(inputString) { // Convert input string to char array let tempArray = inputString.split(""); // Sort tempArray (tempArray).sort(); // Return new sorted string return (tempArray).join(""); } // Driver code let s = "abca"; // Sort s = sortString(s); // Function call permute(0, s); document.write("Total distinct permutations = " + total +"<br>"); // This code is contributed by rag2127 </script>
aabc aacb abac abca acba acab baac baca bcaa caba caab cbaa Total distinct permutations = 12
Complejidad del tiempo: si consideramos que la longitud de la string es N, entonces la complejidad de mi código será O (N log N) para la clasificación y O (N*N!) para la permutación. La complejidad temporal total sería O(N log N + N*N!) que es efectivamente solo O(N*N!).
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