1
$\begingroup$

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)

tries

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?

$\endgroup$
  • 3
    $\begingroup$ Can you provide more background? These statements are out of context. $\endgroup$ – Yuval Filmus Apr 18 '14 at 12:09
  • $\begingroup$ Sure. Could you please follow this link: www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK2/… I don't think it's worth copying that page here -- too big amount. $\endgroup$ – Nik Apr 18 '14 at 22:30
  • 2
    $\begingroup$ The question has to be self-contained. Don't copy everything, only what's relevant. $\endgroup$ – Yuval Filmus Apr 18 '14 at 23:25
  • $\begingroup$ Hi. I improved the question. Hope it makes it more likely to be answered by someone. $\endgroup$ – Nik Apr 19 '14 at 19:20
  • 1
    $\begingroup$ You might be getting the indexing wrong, but the idea is that in a sequence of length $n$, every run is given by two points, so there are $\binom{n}{2}$ of them. $\endgroup$ – Yuval Filmus Apr 20 '14 at 20:20
1
$\begingroup$

Each (non-trivial) run is given by two (different) indices, marking the beginning and end of the run, so if the sequence is of length $n$, there are $\binom{n}{2}$ possible runs. If we only consider maximal runs, there are at most $n$ (or even less, if we don't consider trivial runs).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.