Dada una string str , la tarea es imprimir todas las permutaciones distintas 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 = “abbb”
Salida: [abbb, babb, bbab, bbba]
Entrada: str = “abc”
Salida: [abc, bac, bca, acb, cab, cba]
Enfoque: escriba una función recursiva que genere todas las permutaciones de la string. La condición de terminación será cuando la string pasada esté vacía, en ese caso la función devolverá una ArrayList vacía . Antes de agregar la string generada, simplemente verifique si ya se generó antes para obtener las distintas permutaciones.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java implementation of the approach
import java.util.ArrayList;
public class GFG {
// Function that returns true if string s
// is present in the Arraylist
static boolean isPresent(String s, ArrayList<String> Res)
{
// If present then return true
for (String str : Res) {
if (str.equals(s))
return true;
}
// Not present
return false;
}
// Function to return an ArrayList containing
// all the distinct permutations of the string
static ArrayList<String> distinctPermute(String str)
{
// If string is empty
if (str.length() == 0) {
// Return an empty arraylist
ArrayList<String> baseRes = new ArrayList<>();
baseRes.add("");
return baseRes;
}
// Take first character of str
char ch = str.charAt(0);
// Rest of the string after excluding
// the first character
String restStr = str.substring(1);
// Recurvise call
ArrayList<String> prevRes = distinctPermute(restStr);
// Store the generated sequence into
// the resultant Arraylist
ArrayList<String> Res = new ArrayList<>();
for (String s : prevRes) {
for (int i = 0; i <= s.length(); i++) {
String f = s.substring(0, i) + ch + s.substring(i);
// If the generated string is not
// already present in the Arraylist
if (!isPresent(f, Res))
// Add the generated string to the Arraylist
Res.add(f);
}
}
// Return the resultant arraylist
return Res;
}
// Driver code
public static void main(String[] args)
{
String s = "abbb";
System.out.println(distinctPermute(s));
}
}
[abbb, babb, bbab, bbba]
Optimización: podemos optimizar la solución anterior para usar HashSet para almacenar strings de resultados en lugar de Res ArrayList.