Prima pagină > Articole > Computing > Varia > Recurenţă

Recurenţă

Marţi 6 iunie 2006, de Valentin Murariu

Într-un moment de dat in mintea copiilor, mi-am adus aminte de un joc care era cam aşa: dat fiind un cuvant, să obţin cat mai multe alte cuvinte din literele care compun cuvantul iniţial.

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

Pseudo-cod care foloseşte recurenţă:

func&#355;ie construie&#351;te_lista(le, cle ) {
	ini&#355;ializeaz&#259; cle_retur cu o list&#259; goal&#259;;
	pentru fiecare le' care constituie cle {
		dac&#259; cuvantul ob&#355;inut prin concatenarea le cu le' are sens atunci {
			adaug&#259; la cle_retur noul cuvant (le + le');
			adaug&#259; la cle_retur lista cle ob&#355;inut&#259;
				prin apelul recursiv la 
				construie&#351;te_lista(le + le', cle -le' );
		}
	}
	returneaza cle_retur;
}

M-am gandit să transcriu acest algoritm intr-un limbaj oarecare. După un moment de ezitare in 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:

#!/usr/bin/perl -w

use strict;

##
## Input: word
## Output: Boolean
##
sub makes_sense {
	my $word = shift;
	# No filtering, just say ok all the time
	# However, this could be drastically improved t using a dictionary lookup
	return 1;
}

##
## Input: initial language entity, i.e. word; collection of language entities 
## in form of an array
## Output: list of words that make sense, combinations between initial word 
## and the items of the collection
##
sub build_list {
	# This is the initial language entity
	my $le = shift || '';
	# This is the list of other language entities
	# Acronym for  collection of language entities
	my @cle = @_;
	
	# Initialize the return
	my @words = ();
	
	# This is a counter to browse the array collection of language entities
	my $i;
	for( $i = 0; $i <= $#cle; $i++ ) {
		# Get a copy of the 
		my @second_cle = @cle;
		# Extract the current language entities in the same time as reducing 
		# the collection of language entities
		my $le_prime = splice(@second_cle, $i, 1 );
		# We have now a new word
		my $new_word = $le . $le_prime;
		# Does this make sense ?
		if( makes_sense($new_word ) ) {
			# So, we promote it to the list
			push @words, $new_word;
			# We recursively call the function with a new initial language 
			# entity and a smaller cle
			push @words, build_list($new_word, @second_cle );
		}
	}
	
	# Return whatever is to be returned
	return @words;
}


my $cmd_line = shift || "murariu";

if($cmd_line ) {
	# We provide the list of words
	my @words = ();
	
	my $i;
	for( $i = 0; $i < length($cmd_line ); $i++ ) {
		push @words, substr($cmd_line, $i, 1 );
	}
		
	# Do the work
	my @result = build_list(undef, @words );
	
	# And print the result
	print join('; ', @result );
}

Putem remarca că funcţia makes_sense este fără rost (sic!), dar poate fi imbunătăţită in viitor cu o căutare intr-un dicţionar de cuvinte. Pană 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 decat să filtrez cuvintele care au sens, de exemplu: rad, ard, rudă, aur, dar (Bravo, Radule, ce nume plin de sensuri ascunse ai !).

Trăiască plăcerile obscure ale algoritmilor !