[PHP] Jak wypisać wszystkie anagramy podanego wyrazu (permutacja ciągu)?

Chcesz utworzyć anagramy dla podanego wyrazu, czyli dokonać permutacji wyrazu aby uzyskać wszystkie możliwe jego kombinacje.

Anagramy to wyrazy, które mają takie same litery występujące w takiej samej ilości, ale na innych miejscach, np. "alga" jest anagramem wyrazu "gala".

Tworzenie anagramów z wyrazów może być przydatne w grach słownych. W matematyce permutacja liczb wykorzystywana jest bardzo często, szczególnie w różnych systemach szyfrujących.

Przedstawiony algorytm jest jedną z najbardziej czytelnych implementacji problemu. Ponieważ liczba permutacji rośnie bardzo szybko wraz z ilością liter w wyrazie, musisz zwracać uwagę, aby nie wywoływać funkcji z długimi wyrazami. Zobacz jak szybko wypisać na ekranie wszystkie anagramy dla podanego wyrazu.

<?

function anagramy($wyraz) {

for ($i=0;$i<strlen($wyraz);$i++) {

$znak=$wyraz[$i];

$ile=count($tmp);

if ($ile==0) $tmp[]=$znak;

else {

for($k=0;$k<$ile;$k++) {

$ciag=$tmp[$k];

for($j=0;$j<=strlen($ciag);$j++) {

$new[]= substr($ciag,0,$j).$znak.substr($ciag,$j);

}

}

$tmp=$new;

$new="";

}

}

return $tmp;

}

$tmp = anagramy("123");

for ($i=0;$i<count($tmp);$i++) echo $tmp[$i]."<br>";

?>

Dla 2 liter mamy 2 kombinacje, dla 3 liter już 6, dla 4 liter aż 24, dla 5 liter 120, a dla 6 liter 720 kombinacji. Dla 8 liter istnieje 40320 kombinacji!

Zasada działania algorytmu jest prosta. Pobiera on poszczególne litery i tworzy ich kombinację. Niech naszym ciągniem znaków będzie "123". Bierzemy pierwszą literę (akurat tak się składa, że to cyfra) i otrzymujemy:

1

Teraz bierzemy drugą literę i umieszczamy ją pomiędzy już istniejące. Ponieważ litera jest jedna, to kolejną dostawiamy z przodu i z tyłu. Mamy już dwie kombinacje, które pamiętamy w tablicy $tmp.

21

12

Z tablicy $tmp pobieramy poprzednie kombinacje (dwie) i ponownie uzupełniamy je trzecim znakiem, a całość zapisujemy jest w tablicy $new. Tym razem kombinacji jest sześć.

321

231

213

312

132

123

W przykładzie dobrze widać, jak znak "3" wkładany jest pomiędzy poprzednie kombinacje ze znakami "1" i "2". Ponieważ ciąg miał trzy znaki na tym kończymy i funkcja zwraca nam tablicę anagramów.

Teraz pozostaje wypisać anagramy na ekran, co można z powodzeniem wykonać w pętli for. A oto wszystkie anagramy dla słowa "rady":

adry adyr ardy aryd aydr ayrd

dary dayr dray drya dyar dyra

rady rayd rday rdya ryad ryda

yadr yard ydar ydra yrad yrda

---