Dyck words

A Dyck Word of order $n is a string of length 2 × $n consisting of $n ‘U’ (Up) characters and $n ‘D’ (Down) characters such that no initial prefix of the string contains more ‘D’s than ‘U’s.

Write a script to return a list of all valid Dyck words of length 2 × $n, sorted in lexicographical (alphabetical) order.

Examples

Example 1
Input: $n = 1
Output: ('UD')

Example 2
Input: $n = 2
Output: ('UDUD','UUDD')

Example 3
Input: $n = 3
Output: ('UDUDUD', 'UDUUDD', 'UUDDUD', 'UUDUDD', 'UUUDDD')

Example 4
Input: $n = 0
Output: ('')

Example 5
Input: $n = 4
Output: ('UDUDUDUD', 'UDUDUUDD', 'UDUUDDUD', 'UDUUDUDD', 'UDUUUDDD',
         'UUDDUDUD', 'UUDDUUDD', 'UUDUDDUD', 'UUDUDUDD', 'UUDUUDDD',
         'UUUDDDUD', 'UUUDDUDD', 'UUUDUDDD', 'UUUUDDDD')

Analysis

Walther von Dyck
(1856-1934)

Walther von Dyck was a German mathematician who rose to become Rector of the Technical University of Munich. He established the basis of combinatorial group theory.

The concept of Dyck words is named after him, and they have practical use in areas such as the parsing of mathematical expressions, where '(' and ')' follow the same rules as 'U' and 'D' in today's challenge.

My first thought in solving the challenge was to generate all the unique permutations of - say - UUUDDD, and check which of them met Dyck's condition. That works of course, but it quickly gets too slow: I could handle up to $n == 6 while I drank a cup of coffee, but $n == 10 still hadn't finished during my lunch break.

My second thought was to use recursion: start with one 'U' and steadily add further Us (up to $n of them) and more Ds (up to the number of Us already used), and recording the trial as a valid word if all $n Us and Ds have been used.

And that is the solution I have submitted.

It handles up to $n == 10 in a few seconds and finds the 742 900 qualifying words for $n == 13 in under 20 seconds on my quite slow processor. Not many mathematical expressions have more than 13 pairs of nested brackets, so I think that will do.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/388/1

use v5.26;    # The Weekly Challenge - 2026-08-24
use utf8;     # Week 388 - task 1 - Dyck words
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

my ($n, %solutions);

dyck_words(6);

sub dyck_words {
    $n = $_[0];
    add_next('U', 1, 0);
    say qq[\nInput:  \$n = $n];
    say q[Output: ] . join(', ', sort keys %solutions) .
        q[ (] . (scalar keys %solutions) . q[)];
}

sub add_next {
    
    my ($word, $used_Us, $used_Ds);
    
    # initialise
    ($word, $used_Us, $used_Ds) = @_;
    
    # check for solution
    if ($used_Ds == $n and $used_Us == $n) {
        $solutions{$word} = 1;
        return;
    }
    
    # can add a U
    if ($used_Us < $n) {
        add_next($word . 'U', $used_Us + 1, $used_Ds + 0);
    }
    
    # can add a D
    if ($used_Ds < $used_Us) {
        add_next($word . 'D', $used_Us + 0, $used_Ds + 1);
    }
}

16 lines of code

Output from script

Input:  $n = 6
Output: UDUDUDUDUDUD, UDUDUDUDUUDD, UDUDUDUUDDUD, UDUDUDUUDUDD,
   UDUDUDUUUDDD, UDUDUUDDUDUD, UDUDUUDDUUDD, UDUDUUDUDDUD,
   UDUDUUDUDUDD, UDUDUUDUUDDD, UDUDUUUDDDUD, UDUDUUUDDUDD,
   UDUDUUUDUDDD, UDUDUUUUDDDD, UDUUDDUDUDUD, UDUUDDUDUUDD,
   UDUUDDUUDDUD, UDUUDDUUDUDD, UDUUDDUUUDDD, UDUUDUDDUDUD,
   UDUUDUDDUUDD, UDUUDUDUDDUD, UDUUDUDUDUDD, UDUUDUDUUDDD,
   UDUUDUUDDDUD, UDUUDUUDDUDD, UDUUDUUDUDDD, UDUUDUUUDDDD,
   UDUUUDDDUDUD, UDUUUDDDUUDD, UDUUUDDUDDUD, UDUUUDDUDUDD,
   UDUUUDDUUDDD, UDUUUDUDDDUD, UDUUUDUDDUDD, UDUUUDUDUDDD,
   UDUUUDUUDDDD, UDUUUUDDDDUD, UDUUUUDDDUDD, UDUUUUDDUDDD,
   UDUUUUDUDDDD, UDUUUUUDDDDD, UUDDUDUDUDUD, UUDDUDUDUUDD,
   UUDDUDUUDDUD, UUDDUDUUDUDD, UUDDUDUUUDDD, UUDDUUDDUDUD,
   UUDDUUDDUUDD, UUDDUUDUDDUD, UUDDUUDUDUDD, UUDDUUDUUDDD,
   UUDDUUUDDDUD, UUDDUUUDDUDD, UUDDUUUDUDDD, UUDDUUUUDDDD,
   UUDUDDUDUDUD, UUDUDDUDUUDD, UUDUDDUUDDUD, UUDUDDUUDUDD,
   UUDUDDUUUDDD, UUDUDUDDUDUD, UUDUDUDDUUDD, UUDUDUDUDDUD,
   UUDUDUDUDUDD, UUDUDUDUUDDD, UUDUDUUDDDUD, UUDUDUUDDUDD,
   UUDUDUUDUDDD, UUDUDUUUDDDD, UUDUUDDDUDUD, UUDUUDDDUUDD,
   UUDUUDDUDDUD, UUDUUDDUDUDD, UUDUUDDUUDDD, UUDUUDUDDDUD,
   UUDUUDUDDUDD, UUDUUDUDUDDD, UUDUUDUUDDDD, UUDUUUDDDDUD,
   UUDUUUDDDUDD, UUDUUUDDUDDD, UUDUUUDUDDDD, UUDUUUUDDDDD,
   UUUDDDUDUDUD, UUUDDDUDUUDD, UUUDDDUUDDUD, UUUDDDUUDUDD,
   UUUDDDUUUDDD, UUUDDUDDUDUD, UUUDDUDDUUDD, UUUDDUDUDDUD,
   UUUDDUDUDUDD, UUUDDUDUUDDD, UUUDDUUDDDUD, UUUDDUUDDUDD,
   UUUDDUUDUDDD, UUUDDUUUDDDD, UUUDUDDDUDUD, UUUDUDDDUUDD,
   UUUDUDDUDDUD, UUUDUDDUDUDD, UUUDUDDUUDDD, UUUDUDUDDDUD,
   UUUDUDUDDUDD, UUUDUDUDUDDD, UUUDUDUUDDDD, UUUDUUDDDDUD,
   UUUDUUDDDUDD, UUUDUUDDUDDD, UUUDUUDUDDDD, UUUDUUUDDDDD,
   UUUUDDDDUDUD, UUUUDDDDUUDD, UUUUDDDUDDUD, UUUUDDDUDUDD,
   UUUUDDDUUDDD, UUUUDDUDDDUD, UUUUDDUDDUDD, UUUUDDUDUDDD,
   UUUUDDUUDDDD, UUUUDUDDDDUD, UUUUDUDDDUDD, UUUUDUDDUDDD,
   UUUUDUDUDDDD, UUUUDUUDDDDD, UUUUUDDDDDUD, UUUUUDDDDUDD,
   UUUUUDDDUDDD, UUUUUDDUDDDD, UUUUUDUDDDDD, UUUUUUDDDDDD (132)