Math::DyckWords - Perl module for generating Dyck words. Dyck words are named after the mathematician Walther von Dyck.
use Math::DyckWords qw( dyck_words_by_lex dyck_words_by_position dyck_words_by_swap ranking unranking catalan_number ); @words = dyck_words_by_lex( 4 ); @words = dyck_words_by_position( 4 ); @words = dyck_words_by_swap( 4 ); $rank = ranking( '01010101' ); $word = unranking( 3, 2 );
Dyck words are even numbered string of X's and Y's, or 0's and 1's, or any other binary alphabet for that matter, such that no initial segment has more Y's or 1's. The following are the Dyck words of length 2n where n = 3:
000111 010011 010101 001101 001011
Another common use of Dyck words is in dealing with the balanced parenthesis problem. Substituting the left and right parentheses for the 0's an 1's listed above we have:
((())) ()(()) ()()() (())() (()())
There is also a relationship between Dyck words and Catalan numbers. Catalan numbers have many applications in combinatorics and consists of a sequence of ever increasing integers following the formula:
The first few numbers in the Catalan sequence are:
1, 1, 2, 5, 14, 132, 429, 1430, 4862, 16796, 58786, 208012
The relationship between Dyck words and the Catalan sequence can be easily seen as the nth Catalan number is equal to the number of permutations, or unique Dyck words of length 2n. For example, the 3rd Catalan number, using a zero index, is 5. This is the same number of Dyck words of length 2n where n = 3.
The algorithms in this module are based on those presented in the scholarly paper "Generating and ranking of Dyck words" by Zoltan Kasa available on-line at http://arxiv4.library.cornell.edu/pdf/1002.2625, and the provide three different Dyck word generators - lexigraphical, positional, and one that generates Dyck words by swapping characters.
None by default.
- dyck_words_by_lex( $n )
This algorithm returns a list of all Dyck words of length 2n in ascending lexicographic order, i.e. 000111, 001011, 001101, 010011, 010101
- dyck_words_by_position( $n )
This algorithm returns a list of all Dyck words of length 2n in descending lexicographic order, i.e. 010101, 010011, 001101, 001011, 000111.
- translate_positions( @p )
This function translates an array of integer values indicating the position of 1's in the resultant Dyck word, and is called by the dyck_words_by_position function.
- dyck_words_by_position( $n )
This algorithm returns a list of all Dyck words of length 2n in no particular order, i.e. 010101, 001101, 001011, 000111, 010011. This is done by changing the first occurrence of '10' to '01'.
- monotonic_path_count( $n, $i, $j )
Ranking Dyck words means to determine the position of a Dyck word in a given ordered sequence of all Dyck words. For ranking these words we will use the following function, where f(n,i,j) represents the number of paths between (0,0) and (i,j) not crossing the diagonal x = y of the grid.
- positions( $w )
This function converts a Dyck word string of 1's and 0's into a list of positions where the 1's are located, i.e. 2468 => 01010101
- ranking( $w )
This function returns the rank of an individual Dyck word $w in the list of all Dyck words of the same length.