view release on metacpan or  search on metacpan

lib/Math/DyckWords.pm  view on Meta::CPAN

#######################################################################
# $Id: DyckWords.pm,v 1.2 2010/04/14 03:41:06 mmertel Exp $

=head1 NAME

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

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

=head1 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.

=head1 EXPORT

None by default.

=cut

package Math::DyckWords;

use 5.006;
use strict;
use warnings;

use Carp;
use Data::Dumper;
use Math::BigInt;
use Exporter;

our $VERSION = '0.03';
our @ISA = qw( Exporter );
our @EXPORT_OK = qw( dyck_words_by_lex
                     dyck_words_by_position
                     dyck_words_by_swap
                     ranking
                     unranking
                     catalan_number );

=head1 FUNCTIONS

=over

=item 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

=back

=cut

my @words;

lib/Math/DyckWords.pm  view on Meta::CPAN

    my @c = ( 2 );
    my $n = scalar @b;
    for( my $j = 2; $j <= $n; $j++ ) {
	    $c[ $j - 1 ] = $b[ $j - 2 ] + 1 > $j * 2
	                 ? $b[ $j - 2 ] + 1
                 : $j * 2;
    }
    my $nr = 1;
    for( my $i = 1; $i <= $n - 1; $i++ ) {
	    for( my $j = $c[ $i - 1]; $j <= $b[ $i - 1] - 1; $j++ ) {
	        $nr = $nr + monotonic_path_count( $n, $n - $i, $n + $i - $j );
	    }
    }
    return $nr;
}

=over

=item unranking( $n, $r )

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

=back

=cut

sub unranking( $$ ) {
    my ( $n, $nr ) = @_;

    # initialize the dyck word to all '0'
    my @b = ( '0' x ( $n * 2 ) );

    $nr--;

    for( my $i = 1; $i <= $n; $i++ ) {
	    $b[ $i ] = $b[ $i - 1 ] + 1 > $i * 2
                 ? $b[ $i - 1 ] + 1
                 : $i * 2;

	    my $j  = $n + $i - $b[ $i ];
	    my $np = monotonic_path_count( $n, $n - $i, $j );

	    while( $nr >= $np && ( $b[ $i ] < $n + $i ) ) {
	        $nr      = $nr - $np;
	        $b[ $i ] = $b[ $i ] + 1;
	        $j       = $j - 1;
            $np      = monotonic_path_count( $n, $n - $i, $j );
	    }
    }
    # discard the zeroth element of the list of positions
    shift @b;

    return translate_positions( @b );
}

=over

=item catalan_number( $n )

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

=back

=cut

sub catalan_number( $ ) {
    my $x = shift;

    my $X = Math::BigInt->new( $x );
    my $Y = $X->copy;
    my $Z = $X->copy;

    return $X->bmul( 2 )->bfac->bdiv(
        $Y->bfac->bmul( $Z->badd( 1 )->bfac )
    );
}

1;