Problem Detail: I am reading The Algorithm Design Manual, 2nd Edition. The book gives an example task and then explains how to solve it step by step. (The task and solution is detailed
here)
But I don’t follow one step from the solution. That step doesn’t contain enough details for me so I don’t understand it. I’m asking if someone can explain it. Below I rewrote the task in a shorter form than in the book: Given n ordered strings (lets call them rules) of m characters. The strings are indexed starting from 1 (not 0) The goal is to construct the trie with the minimum possible number of edges. The leaves of the resulting trie (each leaf represents a string) have to be in the same exact order as the given collection of strings. We are free to pick an arbitrary character position on each step of constructing the trie (e. g., we are free to start constructing the trie from character position 2 as opposed to starting from 1). Thanks to this ability we can minimize the built trie. Lets call picking a character – probing. Example: From the four rules below it’s possible to build different tries depending on the order of picking characters from the strings. S1: (a,a,a) S2: (b,a,a) S3: (c,b,b) S4: (d,b,b)
The book says that
Probing at the p-th position, 1 <= p <= m, partitioned the rules into runs R1,…,Rr, where each rule in a given run Rx = Si,…,Sj had the same character value of Si[p]. Since the rules were ordered, each node in the subtree must represent the root of a run of consecutive rules, so there were only ${{n}choose{2}}$ possible nodes to choose from for this tree… … The rules in each run must be consecutive, so there are only ${{n}choose{2}}$ possible runs to worry about.
My question: How does the fact the rules are consecutive lead to the inference that there are ${{n}choose{2}}$ possible nodes/runs after probing at the p-th position?
Asked By : Nik
Related
