2
$\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$
7
  • 3
    $\begingroup$ Can you provide more background? These statements are out of context. $\endgroup$ Apr 18, 2014 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$
    – Myk
    Apr 18, 2014 at 22:30
  • 2
    $\begingroup$ The question has to be self-contained. Don't copy everything, only what's relevant. $\endgroup$ Apr 18, 2014 at 23:25
  • $\begingroup$ Hi. I improved the question. Hope it makes it more likely to be answered by someone. $\endgroup$
    – Myk
    Apr 19, 2014 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$ Apr 20, 2014 at 20:20

1 Answer 1

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 and acknowledge you have read our privacy policy.

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