/ 
DyckWords-0.02
River stage zero No dependents
/ Math::DyckWords

NAME

Math::DyckWords - Perl module for generating Dyck words. Dyck words are named after the mathematician Walther von Dyck.

SYNOPSIS

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 );

DESCRIPTION

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:

(2n)!/(n!(n+1)!)

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.

EXPORT

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.

unranking( $n, $r )

This function returns the rank $r Dyck word of length $n.

catalan_number( $n )

Using the formula - (2n)!/(n!(n+1)!) - this function returns the corresponding number $n from the Catalan sequence.