Buna ziua doamnelor si domnilor si bine v-am regasit. Ma numesc Zero Davila, vom construii un generator de anagrame, si va voi familiariza cu un altgoritm folosit pentru a verifica toate permutarile posibile ale unui sir de caractere. Folosind algoritmul vom crea un generator de anagrame care le va genera intr-o ordine lexicografica. Rezultatele vor avea o radacian,prima data vor avea un caracter in fata si apoi va genera toate permutarile care incep cu acel caracter, si va continua in felul asta pana cand toate caractere oferite sunt folosite. Pentru ca stringul introdus de noi are 3 caractere, inseamna ca numarul de permutari posibile sunt 3! / 1!. Daca vreoun caracter ar fi avut vreo duplicare, ar fi fost 4! / 2! permutari.
Deci pentru ABC avem 3 X 2 X 1, adica 6. Daca am avea ca input AABC, numaratoarea pentru A ar incepe de la 2, iar permutarile stringului ar fi fost 4! / 2! deci 12. Daca am avea ca input AABBBC permutarile ar fi fost 6! / 2! * 3! care face 60, pentru ca avem 2 duplicari ale lui A si 3 duplicari ale lui B. Numaratoarea fiecarui caracter de care vom tine cont cu un array denumit count denota daca caracterul e disponibil sau nu. Un caracter e disponibil daca are o numaratoare mai mare decat 0. La numaratoarea noastra toate caracterele au ori 1 ori 0, dar asta e doar pentru ca nu avem duplicari. Cand numaratoarea e 0, 0, 0, inseamna ca array-ul in care continem rezultatul e plin, asa ca vom afisa rezultatul. Algoritmul o va lua de la stanga la dreapta si va lua primul caracter disponibil, adica cand numaratoarea sa e mai mare decat 0. Apoi vom plasa caracterul in pozitia sa corespunzatoare in array-ul care
va contine rezultatul prin a vedea la ce nivel de recursivitate suntem. Daca avem un string cu 3 caractere, vom avea un arbore cu 3 nivele de recursivitate. Daca suntem la primul nod in arbore si anume pozitia 0, atunci vom pune caracterul in pozitia 0 al array-ului care va contine rezultatul. Si apoi, pentru ca algoritmul e recursiv, vom face acelasi lucru dupa ce decrementam numaratoarea fiindca am folosit deja acel caracter. Cand ne intoarcem inapoi in arbore, restabilim numaratoarea, si cautam urmatorul caracter disponibil din dreapta pentru a incepe alta
ramura.
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class StringPermutation {
public List<String> permute(char input[]) {
Map<Character, Integer> countMap = new TreeMap<>();
for (char ch : input) {
countMap.compute(ch, (key, val) -> {
if (val == null) {
return 1;
} else {
return val + 1;
}
});
}
char str[] = new char[countMap.size()];
int count[] = new int[countMap.size()];
int index = 0;
for (Map.Entry<Character, Integer> entry : countMap.entrySet()) {
str[index] = entry.getKey();
count[index] = entry.getValue();
index++;
}
List<String> resultList = new ArrayList<>();
char result[] = new char[input.length];
permuteUtil(str, count, result, 0, resultList);
return resultList;
}
public void permuteUtil(char str[], int count[], char result[], int level, List<String> resultList) {
if (level == result.length) {
resultList.add(new String(result));
return;
}
for (int i = 0; i < str.length; i++) {
if (count[i] == 0) {
continue;
}
result[level] = str[i];
count[i]–;
permuteUtil(str, count, result, level + 1, resultList);
count[i]++;
}
}
private void printArray(char input[]) {
for (char ch : input) {
System.out.print(ch);
}
System.out.println();
}
public static void main(String args[]) {
StringPermutation sp = new StringPermutation();
sp.permute(„ABC”.toCharArray()).forEach( s -> System.out.println(s));
}
}
Radacina
______________|______________
| | |
A B C
Nivelul de recursivitate : Rezultate :
| |A|B|C|
|__ ___________|1|1|1|___________ 1. |A|B|C|
| | | | 2. |A|C|B|
| V V V
| |A|B|C| |A|B|C| |A|B|C| 3. |B|A|C|
|_0 ______|0|1|1| __|1|0|1|__ |1|1|0|______ 4. |B|C|A|
| | | | | | |
| V V V V V V 5. |C|A|B|
| |A|B|C| |A|B|C| |A|B|C| |A|B|C| |A|B|C| |A|B|C| 6. |C|B|A|
_|_1 |0|0|1| |0|1|0| |0|0|1| |1|0|0| |0|1|0| |1|0|0| A
|| | | | | | | |
|| V V V V V V |
|| |A|B|C| |A|B|C| |A|B|C| |A|B|C| |A|B|C| |A|B|C| |
_||_2 |0|0|0| |0|0|0| |0|0|0| |0|0|0| |0|0|0| |0|0|0| |
||| |
||| R1 R2 R3 R4 R5 R6 |
||| |
||| |________| |_________| |________| |
||| |___________________|___________________| |
||| | | | |
||| Rez(1,2) Rez(3,4) Rez(5,6) |
||| ___ ___ ___ ___ ___ ___ |
|||______0 |A| |A| |B| |B| |C| |C| |
||_______1 |B| |C| |A| |C| |A| |B| ___________|
|________2 |C| |B| |C| |A| |B| |A|