Use unit-cost insertion, deletion and substitution of one symbol. Their minimum total cost is the edit distance. Let be the edit distance between the first symbols of the first sequence and the first of the second. Initialize and . For computeThe cases delete the final source symbol, insert the final target symbol, or align the two final symbols, paying one for substitution and zero for a match. Every optimal alignment ends in one of these cases, and each case extends a valid shorter alignment. Induction on proves the dynamic programming recurrence correct.
Fill rows or columns in increasing order so every dependency is already available. There are entries with constant work per interior entry: running time for nonempty sequences, or including the boundary cases. The full table has space complexity ; two rows give auxiliary space when only the distance is wanted. Predecessor choices in the full table recover an optimal edit sequence.
Given the target's current heap index , remove it as follows. If , discard the last entry. Otherwise replace by and reduce by one. If the replacement is larger than its parent in a rooted tree, use sift up; otherwise use the maximum-oriented sift down from .
Only comparisons incident to the replacement can initially violate the heap order. If it exceeds its parent, it also dominates the old children because the old key dominated those children and was no larger than the parent; an upward repair suffices. Otherwise the upward comparison is valid and only a downward repair can be needed. Thus removal takes worst-case time after the location is known. Searching an unindexed heap for an arbitrary specified key can instead require time; the logarithmic bound does not include such a search.
A maximum priority queue stores keyed entries and supports insertion, inspection and removal of an entry with greatest key, and key increases. A max-heap gives the following running times, with the size/capacity cost of the backing array accounted for separately:
maximum: return the root key in time.insert: append at the next available leaf, then use sift up until the heap order holds, in time.extractMaximum: save the root, replace it by the last entry, reduce the size, and use sift down, in time.increaseKey(i,k): reject ; otherwise set the new key and use sift up, in time.isEmptyandsize: inspect the stored size in time; construct a queue from keys by bottom-up heap construction in time.
Assume ascending sorted arrays; descending storage can be accessed in reverse index order without copying. Among entries, the requested rank is in ascending order, not . Repeated values occupy repeated ranks.
Choose entries from the first array and from the second, using their prefixes. The feasible range is . Write , , and similarly at , with missing left endpoints replaced by and missing right endpoints by . These are conceptual sentinels, not extra stored entries.
Use binary search over the feasible values of :
- If , there are too many entries from on the left; decrease the upper bound to .
- If , there are too few entries from on the left; increase the lower bound to .
- Otherwise return .
For correctness, in the last case every left entry is no greater than every right entry, and exactly entries lie on the left. Their maximum is therefore the -th smallest entry. The failed inequalities are monotone in the searched index: increasing raises the boundary and decreases the boundary, so it cannot repair ; the other case is symmetric. A partition of the first entries of a merged ordering supplies an admissible solution, including ties. Each step halves an interval with at most choices, giving running time and auxiliary space. This is a two-sorted-array order statistic without constructing the merged array.
For an ascending sorted array, maintain a candidate interval initially containing every index. Compare the target with the middle entry at . Equality returns ; if the target is smaller, replace by ; if larger, replace by . An empty interval reports absence.
The loop invariant is that any target occurrence still possible lies inside the candidate interval. Sortedness justifies discarding the appropriate half after each unequal comparison. The interval length decreases to at most half its previous length, establishing termination and correctness. After unsuccessful comparisons there are at most candidates, so at most comparisons suffice for . Each iteration uses constant work on a random-access array. Thus binary search takes running time, conventionally written for nontrivial input sizes. Empty input is handled in constant time.
A divide-and-conquer algorithm handles a small input directly; otherwise it divides the input into smaller instances, recursively solves them, and combines their answers. With equally sized subproblems of size approximately and nonrecursive work , its recurrence relation has the form , with constant-size base cases, and .
- If , then .
- If , then .
- If and the regularity condition holds eventually for some , then .
For the common extended middle case, with fixed gives . A recursion tree explains the three cases: work is dominated by its leaves, spread across comparable levels, or dominated by its top levels. The regularity condition in the last case is part of the theorem, not an optional simplification.
cp :: [[a]] -> [[a]]
cp [] = [[]]
cp (xs:xss) = fairPair (:) xs (cp xss)The empty family has one selection, the empty selection. For a nonempty finite family, each selection consists uniquely of one first-factor occurrence followed by a selection from the remaining factors. Induction on the number of factors, together with the fairness of
fairPair, proves that every such selection is produced and no invalid selection is introduced. Infinite factors are allowed: in particular, the three-factor example is enumerated fairly. If any factor is empty, the finite-family computation returns the empty product.The printed hypothesis also permits an infinite outer proper lazy list. No function can satisfy the full enumeration requirement for all such inputs. Take
repeat [0,1]. Its mathematical Cartesian product contains every infinite binary sequence and is uncountable. If a result list enumerated these sequences as , the binary sequence with would differ from the -th listed sequence at position , contradicting completeness. This is an uncountability obstruction to enumerating infinite Cartesian products. The finite-outer qualification is a necessary repair to the specification, not a restriction imposed for convenience by the code. There are unlisted articles, also show them or only show them.