Sign in to watch this lesson
Advanced - Combinatorics, Games and Puzzles Ā· 4:41
Balanced Bracket Sequences
Four operations on balanced bracket sequences, all in linear time after one quadratic table. A depth counter (or a stack, when there are several kinds of bracket) checks a sequence, the next sequence in sorted order flips the rightmost opening bracket that still has something open to its left and refills the rest, and a table of ways to finish turns a sequence into its rank and a rank back into a sequence. We also see why those counts need 64-bit and then 128-bit integers.
You will learn
- Check a bracket sequence in one pass with a depth counter, and with a stack when there are several kinds of bracket
- Count balanced sequences with n pairs and k kinds as C_n * k^n
- Step to the lexicographically next balanced sequence in O(n) by flipping the rightmost '(' that has an unclosed bracket to its left and refilling the suffix
- Rank and unrank sequences with the ways-to-finish table ways[r][b] = ways[r-1][b-1] + ways[r-1][b+1], using 64- or 128-bit counts