Encuentra todas las permutaciones de una cadena dada en Java

La permutación es la técnica matemática para determinar el número de arrays posibles en un conjunto cuando el orden del array es importante.

Permutaciones de una cadena mediante recursividad

La función permutationFinder(String str) es recursiva e imprime cada permutación de la cadena pasada. La variable Set se utiliza para almacenar las permutaciones de una cadena de Java para que los duplicados se eliminen automáticamente. Cortamos nuestras palabras, tomando una letra a la vez en nuestra cadena, y tratamos las letras restantes por separado.

La función insertChar inserta el primer carácter para obtener la lista completa de permutaciones para la cadena que pasamos.

Comenzamos con la cadena “ABC”, iteramos a través de ella, una letra a la vez. Separamos nuestro carácter inicial, A, y los restantes son BC. Ahora iteramos a través del rem y encontramos las permutaciones de las letras restantes. El proceso se explica con más detalle a continuación.

La función permutationFinder() se activa hasta que no tenemos nada que cortar; por eso obtenemos rem = "". En este punto, agregamos "" a perms y lo devolvemos, que se almacena en la variable Set, words. Además, recuerde que nuestro carácter initial en este momento es C.

Pasamos por encima de cada cadena en las palabras Set. Tenemos strNew como la cadena vacía "", baja al segundo bucle for en este caso, tenemos i=0 que es igual a strNew.length(); así, llamamos al método insertChar("",C,0) con los argumentos en ese punto. Esta llamada devuelve C, que se agrega a perm.

Rompemos el bucle y comprobamos si tenemos asuntos pendientes. Así, en este punto, tenemos nuestro valor initial como B, y las palabras tienen un elemento, que es C. Ahora, el bucle se repite agregando B en diferentes posiciones con C. Así, obtenemos BC y CB como dos elementos dentro de las palabras Set.

En este punto, estamos fuera del bucle y obtenemos el valor initial como A. Repetimos este proceso e insertamos el carácter inicial A en posibles posiciones en nuestras permutaciones anteriores. En primer lugar, para BC, obtenemos ABC BAC y BCA. Del mismo modo, para la segunda permutación, CB, hacemos lo mismo: insertar la primera letra en las posiciones posibles y obtener ACB, CAB y CBA.

import java.util.HashSet;
import java.util.Set;

public class PermutationFinder {
  public static Set<String> permutationFinder(String str) {
    Set<String> perm = new HashSet<String>();
    if (str == null) {
      return null;
    } else if (str.length() == 0) {
      perm.add("");
      return perm;
    }
    char initial = str.charAt(0);
    String rem = str.substring(1);
    Set<String> words = permutationFinder(rem);
    for (String strNew : words) {
      for (int i = 0; i <= strNew.length(); i++) {
        perm.add(insertChar(strNew, initial, i));
      }
    }
    return perm;
  }

  public static String insertChar(String str, char c, int j) {
    String begin = str.substring(0, j);
    String end = str.substring(j);
    return begin + c + end;
  }
  public static void main(String args[]) {
    String s1 = "ABC";
    System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
  }
}

Estas son todas las posibles permutaciones de la cadena “ABC”.

Producción :

Permutations for ABC are: 
[ACB, BCA, ABC, CBA, BAC, CAB]