Recurenţă

, by  Valentin Murariu

Īntr-un moment de dat īn mintea copiilor, mi-am adus aminte de un joc care era cam aşa: dat fiind un cuvānt, să obţin cāt mai multe alte cuvinte din literele care compun cuvāntul iniţial.

Am nevoie de următoarele structuri de date:
- entităţi de limbaj (language entities): le. Poate fi o literă sau un alt cuvānt.
- colecţie de entităţi de limbaj: cle.

Pseudo-cod care foloseşte recurenţă:

funcţie construieşte_lista(le, cle ) {
        iniţializează cle_retur cu o listă goală;
        pentru fiecare le' care constituie cle {
                dacă cuvāntul obţinut prin concatenarea le cu le' are sens atunci {
                        adaugă la cle_retur noul cuvānt (le + le');
                        adaugă la cle_retur lista cle obţinută
                                prin apelul recursiv la
                                construieşte_lista(le + le', cle -le' );
                }
        }
        returneaza cle_retur;
}

M-am gandit să transcriu acest algoritm īntr-un limbaj oarecare. După un moment de ezitare īn care am comparat:
- C, unde le poate fi un sir de caractere iar cle un tablou de pointere la şiruri de caractere
- C++, unde le poate fi un std::string şi cle un std::vector;
- Java, unde le poate fi un String şi cle un List;
- Perl, unde le poate fi un şir de caractere şi cle un tablou;

Am ales Perl, pentru concizia cu care pot scrie următorul cod:

Putem remarca că funcţia makes_sense este fără rost (sic!), dar poate fi īmbunătăţită īn viitor cu o căutare īntr-un dicţionar de cuvinte. Pānă una-alta, filtrarea va fi făcută ulterior de către operatorul uman.

Dacă rulez acest script:

$ ./words.pl radu
r; ra; rad; radu; rau; raud; rd; rda; rdau; rdu; rdua; ru; rua; ruad; rud; ruda; a; ar; ard; ardu; aru; arud; ad; adr; adru; adu; adur; au; aur; aurd; aud; audr; d; dr; dra; drau; dru; drua; da; dar;
daru; dau; daur; du; dur; dura; dua; duar; u; ur; ura; urad; urd; urda; ua; uar; uard; uad; uadr; ud; udr; udra; uda; udar

Nu mai am acum decāt să filtrez cuvintele care au sens, de exemplu: rād, ard, rudă, aur, dar (Bravo, Radule, ce nume plin de sensuri ascunse ai !).

Trăiască plăcerile obscure ale algoritmilor !