Generate in Perl all the Dyck words of length 2N

 The Dyck words are the elements that form the Dyck language and can be defined as any sequence of parenthesis correctly balanced, for example, these are the Dyck words having 3 pairs of parenthesis:

((()))  (()())  (())()  ()(())  ()()()

Also, the number of Dyck words of length 2N is equal to the Nth Catalan number, registered in OEIS as A000108, and the Dyck words can be converted to many geometric representations of the Catalan numbers.

The following program in Perl generates all the Dyck words of length 2N using the characters "0" and "1", receiving N as argument:

#!/usr/bin/perl
# dyck.pl - prints all dyck words of length 2N given N as argument
my $s=('0'x$ARGV[0]).('1'x$ARGV[0]); my $t;
do{
    print $s, "\n";
}while($s=~s/(.*)01(1.*)/$1.'10'.join('',($t=$2)=~m'0'g).join('',$t=~m'1'g)/e);

On each iteration, the last instruction generates the next word transforming the current word by finding the last "011", replacing "01" with "10" and then reordering the other "1" and its following characters (if any) placing first the 0's and then the 1's.

Code explanation: The variables $1 and $2 store the begining and the end of the word found by the regular expression (.*)01(1.*) and the variable $t is used to save the content of $2 because $1 and $2 are rewritten when the other regular expression operators =~ are executed for collect and separate the 0's and the 1's of the end.

For example:

> perl dyck.pl 4
00001111
00010111
00011011
00011101
00100111
00101011
00101101
00110011
00110101
01000111
01001011
01001101
01010011
01010101

Enjoy it!

Generate in Perl the numbers with digits in order

If you try to count using only numbers with all its digits in ascending order, you will get this:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 123, ...

This sequence is registered in OEIS as A009994 - Numbers with digits in nondecreasing order.

Note that all the jumps are located after the last digit becomes 9, because the digit 0 cannot appear after the first occurrence. Considering this, I have created a little Perl program to generate it:

#!/usr/bin/perl
for($_="";;) {
    s/([0-8]?)(9*)$/$2?($1?$1+1:1)x(length($2)+1):length($1)?$1+1:0/e;
    print "$_\n";
}

On each iteration, the regular expression is applied to the variable $_ generating the next number, following this algorithm:

• If there are one or more 9's at the end then:
• If there is a digit X<9 just before the 9's then that digit X and those 9's are all replaced with the digit X+1 repeated as many times as the number of 9's plus one, for example 22499=>22555
• If there is no digit just before the 9's then is considered that the digit is 0 and the same operation is done, for example 999=>1111
• If there are no 9's at the end then:
• If there is a digit X at the end then the digit X is replaced with the digit X+1, for example 133=>134
• If there is no digit in the number then the digit 0 is inserted

I tried to do the code as easy to understand as I could, so you can use it if you need without problem ;-). Thanks for reading!