Permutácia reťazca pomocou spätného algoritmu - java, algoritmus, rekurzia, permutácia, backtracking

Čítal som kód uvedený nižšie na Geeksforgeeks, ale ja jednoducho nemôžem „zabaliť hlavu, ako to funguje! Ak to niekto môže vysvetliť obrázkom.

toto je kód:

static void swap(char a[], int l, int r) {
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}

static void permute(char a[], int l, int r) {
if (l == r)
System.out.println(getString(a));
else {
for (int i = l; i <= r; i++) {
swap(a, l, i);
permute(a, l + 1, r);
swap(a, l, i); // backtrack
}
}
}

odpovede:

Nechápem, kde ste zmätení: poskytli ste obrázok, ktorý mi to celkom jasne vysvetľuje ... mne. :-)

Podmienka ukončenia (spodný riadok diagramu, 2 červené a 1 zelené položky): ak má zoznam iba jeden zostávajúci prvok, nie je kam vymeniť. Permutácia je hotová. spiatočný

Inak ... Pri každej položke, ktorá zostane v poli, prejdite touto pozíciou na najviac dostupné miesto vľavo. Presuňte ukazovateľ „pevný“ o jedno miesto doprava a rutinu zavolajte na zvyšku poľa.

celkovo, toto jednoducho prejde po poli: vyberte každú položku (postupne) na prvú pozíciu; vyberte druhú zvyšnú položku (potom); ... pokračovať do konca zoznamu.

Vyjadruje to niečo pre vás?