Lexicographic Algorithms in Combinatorics and String ProcessingLexicographic ordering — often shortened to “lexicographic” or “lexicographical” — is a fundamental concept that extends the familiar dictionary order to sequences of symbols. It provides a natural, well-defined way to compare sequences (strings, tuples, permutations, combinations) and underpins many algorithms in combinatorics and string processing. This article explains the theory, common algorithmic patterns, practical implementations, and applications, with examples and performance considerations.
What is lexicographic order?
Given an alphabet A whose symbols are totally ordered (for example, characters ‘a’ < ‘b’ < ‘c’ or integers 0 < 1 < 2), lexicographic order compares two sequences element by element from left to right. The first position where the sequences differ determines the ordering. If one sequence is a prefix of the other, the shorter sequence is considered smaller.
Example:
- “apple” < “apricot” because ‘p’ = ‘p’ at positions 1–2, then ‘p’ < ‘r’.
- [1, 2] < [1, 2, 0] because the first is a prefix of the second.
Key fact: Lexicographic order is a total order on the set of finite sequences over a totally ordered alphabet.
Why lexicographic algorithms matter
- They provide a canonical, reproducible ordering for combinatorial objects (permutations, combinations, subsets), which is crucial for enumeration, testing, and exhaustive search.
- They allow efficient generation of the “next” or “previous” combinatorial object without recomputing from scratch.
- Many string-processing routines (sorting, searching, pattern matching, suffix array construction) rely on lexicographic comparisons.
- Lexicographic order maps naturally to numerical encodings (ranking/unranking), enabling compact representations and combinatorial indexing.
Core algorithms and techniques
Next and previous lexicographic permutation (Steinhaus–Johnson–Trotter / std::next_permutation)
Given a permutation of n distinct elements, the classic algorithm to compute the next permutation in lexicographic order is:
- Find the longest non-increasing suffix. Let pivot be the element just before this suffix.
- Find the rightmost successor to pivot in the suffix (the smallest element greater than pivot).
- Swap pivot with successor.
- Reverse the suffix (which was non-increasing) to make it increasing.
This yields the immediate lexicographic successor. Repeating until no pivot exists enumerates all permutations in lexicographic order.
Complexity: O(n) in the worst case per step, but average is often lower; uses O(1) extra space.
Example in C++: std::next_permutation implements this.
Generating combinations in lexicographic order
Common representation: choose k indices 0 ≤ c0 < c1 < … < c{k-1} < n. To get the next combination:
- Find the rightmost index i such that c_i < n – k + i.
- Increment c_i by 1.
- For j from i+1 to k-1 set cj = c{j-1} + 1.
This enumerates all k-combinations of an n-element set in lexicographic order of index sequences. Complexity O(k) per combination.
Variants: Gray-code-like orders minimize changes between successive combinations, useful for incremental updates.
Ranking and unranking
Ranking: map a combinatorial object (e.g., a specific permutation or combination) to its position (rank) in lexicographic order.
Unranking: given a rank, reconstruct the object.
- For combinations: ranks can be computed using binomial coefficients (combinatorial number system, combinadic). Rank formula uses sums of binomial(n – 1 – ci, k – i).
- For permutations: factorial number system (Lehmer code). Compute Lehmer code by counting smaller elements to the right; rank = sum_{i=0}^{n-1} c_i * (n-1-i)!.
Both operations are O(n log n) or O(n) with appropriate data structures (Fenwick tree for counting/inversion queries).
Lexicographic order in strings: suffix arrays and suffix trees
Suffix arrays are arrays of starting positions of all suffixes of a string sorted in lexicographic order. Efficient construction algorithms include:
- Manber & Myers: O(n log n) time using doubling and radix sort.
- SA-IS: linear-time suffix array construction using induced sorting.
- DC3 / skew algorithm: linear time for integer alphabets.
Suffix arrays enable fast pattern matching (binary search over sorted suffixes), computing longest common prefixes (LCP), and solving many string problems (distinct substrings, repeats).
Suffix trees are trie-like structures of all suffixes; they support many operations in linear time but are more memory-intensive.
Lexicographically minimal rotation (Booth’s algorithm)
To find the lexicographically smallest rotation of a string in linear time, Booth’s algorithm uses a failure-function-like scan over the string concatenated with itself, maintaining two candidate starting positions. This is widely used in circular string matching and canonical rotation problems.
Complexity: O(n) time, O(1) extra space.
Implementation patterns and optimizations
- Use radix/counting sorts when alphabet size is small/integer to achieve linear-time steps.
- For ranking/unranking permutations, Fenwick (BIT) or segment trees give O(log n) updates and prefix queries, reducing naive O(n^2) behavior.
- Memory vs speed trade-offs: suffix arrays + LCP arrays are memory-efficient; suffix trees/automata provide richer queries but use more memory.
- Avoid repeated allocation; reuse buffers when iterating through large enumerations.
- Parallelization: independent blocks of the lexicographic space can be generated in parallel if ranks/unranks are available to split ranges.
Applications
- Combinatorial generation: exhaustive search, test-case generation, algorithmic combinatorics.
- Cryptography and coding: enumerating keys or codewords in a canonical order, analyzing permutations.
- Bioinformatics: suffix arrays and minimal rotations for sequence analysis, motif finding.
- Data indexing/search: lexicographic order on strings underlies many search systems and databases.
- Compression: BWT (Burrows–Wheeler Transform) uses lexicographic sorting of rotations as a core step.
Examples
Lexicographic permutations (Python sketch)
def next_permutation(a): # a: list of comparable items n = len(a) i = n - 2 while i >= 0 and a[i] >= a[i+1]: i -= 1 if i == -1: return False j = n - 1 while a[j] <= a[i]: j -= 1 a[i], a[j] = a[j], a[i] a[i+1:] = reversed(a[i+1:]) return True Ranking a permutation (Lehmer code)
def perm_rank(a): n = len(a) rank = 0 bit = Fenwick(n) # 1-indexed BIT for counts for i in range(1, n+1): bit.add(i, 1) for i in range(n): x = a[i] less = bit.sum(x-1) # count of unused elements < x rank = rank * (n - i) + less bit.add(x, -1) return rank Complexity summary
- Next-permutation: O(n) worst-case per step.
- Next-combination: O(k) per step.
- Permutation ranking/unranking: O(n log n) with BIT, O(n^2) naive.
- Suffix array construction: O(n) (SA-IS, DC3) or O(n log n) (doubling).
- Minimal rotation: O(n).
Practical tips
- Use library functions when available (C++ std::next_permutation, language-specific suffix-array libraries).
- Prefer stable, well-tested implementations for critical tasks (SA-IS for large strings).
- When enumerating huge combinatorial spaces, implement checkpoints via ranking to resume or partition work.
- For strings with large alphabets, compress alphabet to ranks to make integer-based algorithms efficient.
Further reading and resources
- Knuth — The Art of Computer Programming, Vol. 4A (combinatorial generation).
- Gusfield — Algorithms on Strings, Trees, and Sequences.
- Original papers: SA-IS, Manber & Myers, Booth’s algorithm, Steinhaus–Johnson–Trotter.
Lexicographic algorithms form a compact, powerful toolkit connecting combinatorics and string processing. Their elegant local operations (find pivot, swap, increment indices) let us traverse enormous discrete spaces methodically, while ranking and unranking provide numerical handles for partitioning and indexing those spaces.
Leave a Reply