Encontre todas as permutações de uma determinada string em Java

A permutação é a técnica matemática para determinar o número de arranjos possíveis em um conjunto quando a ordem do arranjo é importante.

Permutações de uma string usando recursão

A função permutationFinder(String str) é recursiva que imprime cada permutação da string passada. A variável Set é usada para armazenar as permutações de uma string Java para que as duplicatas sejam removidas automaticamente. Cortamos nossas palavras, pegando uma letra de cada vez em nosso barbante, e lidamos com as letras restantes separadamente.

A função insertChar insere o primeiro caractere para obter a lista completa de permutações para a string que passamos.

Começamos com a string “ABC” e a iteramos, uma letra de cada vez. Separamos nosso caractere inicial, A, e os restantes são BC. Agora iteramos por rem e encontramos as permutações para as letras restantes. O processo é explicado com mais detalhes abaixo.

A função permutationFinder() é acionada até que não tenhamos nada para cortar; é por isso que obtemos rem = "". Neste ponto, adicionamos "" a perms e o devolvemos, que é posteriormente armazenado na variável Set, words. Além disso, lembre-se de que nosso caractere initial neste momento é C.

Fazemos um loop em cada string nas palavras Set. Temos strNew como a string vazia "", desce para o segundo for-loop, neste caso, temos i=0 que é igual a strNew.length(); portanto, chamamos o método insertChar("",C,0) com os argumentos nesse ponto. Esta chamada retorna C, que é adicionado a perm.

Nós quebramos o bucle e verificamos se temos negócios pendentes. Assim, neste ponto, temos nosso valor initial como B, e words têm um elemento, que é C. Agora, o loop se repete adicionando B em diferentes posições com C. Assim, obtemos BC e CB como dois elementos dentro das palavras Set.

Neste ponto, estamos fora do loop e obtemos o valor initial como A. Mais adiante, repetimos esse processo e inserimos o caractere inicial A em posições possíveis em nossas permutações anteriores. Em primeiro lugar, para BC, obtemos ABC BAC e BCA. Da mesma forma, para a segunda permutação, CB, fazemos a mesma coisa: inserir a primeira letra nas posições possíveis e obter ACB, CAB e 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));
  }
}

Essas são todas as permutações possíveis da string “ABC”.

Resultado:

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