Dada una string str , la tarea es imprimir todas las permutaciones de str . Una permutación es un arreglo de todo o parte de un conjunto de objetos, con respecto al orden del arreglo. Por ejemplo, las palabras ‘bat’ y ‘tab’ representan dos permutaciones distintas (o arreglos) de una palabra similar de tres letras.
Ejemplos:
Entrada: str = “cd”
Salida: cd dc
Entrada: str = “abb”
Salida: abb abb bab bba bab bba
Enfoque: escriba una función recursiva que imprima cada permutación de la string dada. La condición de terminación será cuando la string pasada esté vacía.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program to print all the permutations // of the given string public class GFG { // Function to print all the permutations of str static void printPermutn(String str, String ans) { // If string is empty if (str.length() == 0) { System.out.print(ans + " "); return; } for (int i = 0; i < str.length(); i++) { // ith character of str char ch = str.charAt(i); // Rest of the string after excluding // the ith character String ros = str.substring(0, i) + str.substring(i + 1); // Recursive call printPermutn(ros, ans + ch); } } // Driver code public static void main(String[] args) { String s = "abb"; printPermutn(s, ""); } }
abb abb bab bba bab bba
Cuando las permutaciones necesitan ser distintas.
Ejemplos:
Entrada: str = “abb”
Salida: abb bab bba
Entrada: str = “geek”
Salida: geek geke gkee egek egke eegk eekg ekge ekeg kgee kege keeg
Enfoque: escriba una función recursiva que imprima distintas permutaciones. Cree una array booleana de tamaño ’26’ que tenga en cuenta el carácter que se está utilizando. Si no se ha utilizado el carácter, se realizará la llamada recursiva. De lo contrario, no haga ninguna llamada. La condición de terminación será cuando la string pasada esté vacía.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program to print all the permutations // of the given string public class GFG { // Function to print all the distinct // permutations of str static void printDistinctPermutn(String str, String ans) { // If string is empty if (str.length() == 0) { // print ans System.out.print(ans + " "); return; } // Make a boolean array of size '26' which // stores false by default and make true // at the position which alphabet is being // used boolean alpha[] = new boolean[26]; for (int i = 0; i < str.length(); i++) { // ith character of str char ch = str.charAt(i); // Rest of the string after excluding // the ith character String ros = str.substring(0, i) + str.substring(i + 1); // If the character has not been used // then recursive call will take place. // Otherwise, there will be no recursive // call if (alpha[ch - 'a'] == false) printDistinctPermutn(ros, ans + ch); alpha[ch - 'a'] = true; } } // Driver code public static void main(String[] args) { String s = "geek"; printDistinctPermutn(s, ""); } }
geek geke gkee egek egke eegk eekg ekge ekeg kgee kege keeg