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. Una permutación no debe tener strings repetidas en la salida.
Ejemplos:
Entrada: str = «aa»
Salida:
aa
Tenga en cuenta que «aa» se imprimirá solo una vez
, ya que no se permiten duplicados.Entrada: str = “ab”
Salida:
ab
ba
Enfoque: escriba una función recursiva que elimine un carácter uno por uno de la string original y genere una nueva string agregando estos caracteres eliminados. La condición base será cuando se hayan utilizado todos los caracteres. En ese caso, inserte la string generada (una permutación de la string original) en un conjunto para evitar duplicados.
A continuación se muestra la implementación del enfoque anterior:
// Java implementation of the approach
import java.util.*;
public class GFG {
static Set<String> hash_Set = new HashSet<>();
// Recursive function to generate
// permutations of the string
static void Permutation(String str, String ans)
{
// If string is empty
if (str.length() == 0) {
// Add the generated permutation to the
// set in order to avoid duplicates
hash_Set.add(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);
// Recurvise call
Permutation(ros, ans + ch);
}
}
// Driver code
public static void main(String[] args)
{
String s = "ab";
// Generate permutations
Permutation(s, "");
// Print the generated permutations
hash_Set.forEach((n) -> System.out.println(n));
}
}
ab ba