Trova tutte le permutazioni di una data stringa in Java

La permutazione è la tecnica matematica per determinare il numero di possibili disposizioni in un insieme quando l’ordine della disposizione è importante.

Permutazioni di una stringa usando la ricorsione

La funzione permutationFinder(String str) è ricorsiva e stampa ogni permutazione della stringa passata. La variabile Set viene utilizzata per memorizzare le permutazioni di una stringa Java in modo che i duplicati vengano rimossi automaticamente. Tagliamo le nostre parole, prendendo una lettera alla volta nella nostra stringa e gestiamo separatamente le lettere rimanenti.

La funzione insertChar inserisce il primo carattere per ottenere la lista completo delle permutazioni per la stringa che abbiamo passato.

Iniziamo con la stringa “ABC”, iteriamo attraverso di essa, una lettera alla volta. Separiamo il nostro carattere iniziale, A, e i restanti sono BC. Ora iteriamo attraverso il rem e troviamo le permutazioni per le lettere rimanenti. Il processo è ulteriormente spiegato di seguito.

La funzione permutationFinder() viene attivata finché non abbiamo nulla da tagliare; ecco perché otteniamo rem = "". A questo punto, aggiungiamo "" a perms e lo restituiamo, che viene ulteriormente memorizzato nella variabile Set, words. Inoltre, ricorda che il nostro carattere initial in questo momento è C.

bucle su ogni stringa nelle parole Set. Abbiamo strNew come stringa vuota "", scende al secondo bucle for in questo caso, abbiamo i=0 che è uguale a strNew.length()); quindi, chiamiamo il metodo insertChar("",C,0) con gli argomenti in quel punto. Questa chiamata restituisce C, che viene aggiunto a perm.

Rompiamo il bucle e controlliamo se abbiamo affari incompiuti. Quindi, a questo punto, abbiamo il nostro valore initial come B, e le words hanno un elemento, che è C. Ora, il bucle si ripete aggiungendo B in posizioni diverse con C. Quindi, otteniamo BC e CB come due elementi all’interno delle parole Set.

A questo punto, siamo fuori dal giro e otteniamo il valore initial come A. Ripetiamo ulteriormente questo processo e inseriamo il carattere iniziale A in posizioni possibili nelle nostre precedenti permutazioni. In primo luogo, per BC, otteniamo ABC BAC e BCA. Allo stesso modo, per la seconda permutazione, CB, facciamo la stessa cosa: inseriamo la prima lettera nelle posizioni possibili e otteniamo 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));
  }
}

Queste sono tutte le possibili permutazioni della stringa “ABC”.

Produzione:

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