TAOCP 5 Exercise 20

We are given \(N = 1000\) words \(x_1, x_2, \dots, x_{1000}\), each of length 30 bits.

taocpmathematicsalgorithmsvolume-3medium

Section 5: Introduction to Sorting

Exercise 20. ▶ [25] Given a file containing 1000 30-bit words $x_1, \ldots, x_{1000}$, how would you prepare a list of all pairs $(x_i, x_j)$ such that $x_i = x_j$ except in at most two bit positions?

Verified: yes
Solve time: 25m58s

Solution

We are given (N = 1000) words (x_1, x_2, \dots, x_{1000}), each of length 30 bits. The task is to list all pairs ((x_i, x_j)) with (i < j) whose Hamming distance (d(x_i, x_j)) is at most 2 (i.e., the words are equal or differ in one or two bit positions).

Algorithm

  1. Sort and group identical words.
    Form an array of records ((x_k, k)) for (k = 1,\dots,1000). Sort this array by the word value (x_k) (and secondarily by index (k) to keep indices within a group in increasing order). Scan the sorted array to identify the distinct values (U[1] < U[2] < \dots < U[M]) ((M \le 1000)). For each distinct value (U[m]) store the list (L[m]) of original indices that have this value; the lists are naturally ordered by increasing index because of the secondary sort key.
    While scanning, for every group (L[m]) output all pairs ((i, j)) with (i, j \in L[m]) and (i < j). These are exactly the pairs with distance 0.

  2. Find pairs at distance 1 or 2.
    For each distinct value (U[m]) ((m = 1) to (M)):

    • Let (w = U[m]).
    • Generate the 30 words (v = w \oplus (1 \ll b)) for (b = 0,\dots,29) (distance 1).
    • Generate the (\binom{30}{2} = 435) words (v = w \oplus (1 \ll b_1) \oplus (1 \ll b_2)) for (0 \le b_1 < b_2 \le 29) (distance 2).
    • For each generated word (v), binary‑search (v) in the sorted array (U).
    • If (v) is found at position (l) with (l > m), then for every (i \in L[m]) and (j \in L[l]) output the ordered pair ((\min(i,j), \max(i,j))). Because (l > m), every unordered pair of distinct values is considered exactly once; taking the minimum and maximum guarantees (i < j) in the output.

  3. Result. The union of the pairs produced in steps 1 and 2 is the required list.

Correctness

We prove that the algorithm outputs exactly the set ({, (i,j) \mid 1 \le i < j \le 1000,; d(x_i, x_j) \le 2 ,}).

Soundness.

  • Step 1 outputs only pairs from the same group (L[m]). By construction all indices in (L[m]) have the same word value (U[m]), so their Hamming distance is 0. The condition (i < j) is enforced explicitly.
  • Step 2 considers a pair of distinct values (U[m]) and (U[l]) with (m < l) and (U[l]) generated from (U[m]) by flipping one or two bits. Hence (d(U[m], U[l]) \in {1,2}). For any (i \in L[m]) and (j \in L[l]) we have (d(x_i, x_j) = d(U[m], U[l]) \le 2). The output uses ((\min(i,j), \max(i,j))), which satisfies (i < j). No other pairs are output.

Completeness.
Take any pair ((i,j)) with (i < j) and (d(x_i, x_j) \le 2). Let (a = x_i) and (b = x_j).

  • If (a = b) then (i) and (j) belong to the same group (L[m]). Step 1 outputs all pairs with (i < j) from that group, so ((i,j)) is output.
  • If (a \ne b) then (d(a,b) \in {1,2}). Let (m) and (l) be the positions of (a) and (b) in (U); without loss of generality (m < l) (since (U) is strictly increasing). When processing (m) in step 2 we generate all words at distance 1 and 2 from (a); in particular (b) is generated. The binary search finds (b) at position (l > m). The algorithm then iterates over all (i' \in L[m]) and (j' \in L[l]), which includes the original (i) and (j). The pair is emitted as ((\min(i,j), \max(i,j)) = (i,j)) because (i < j). Thus ((i,j)) is output exactly once.

No duplicates.

  • Distance‑0 pairs are produced only in step 1, and each unordered pair of indices from the same group appears exactly once because we iterate with (i < j).
  • For distance 1 or 2, each unordered pair of distinct values ({a,b}) is considered exactly once: when the smaller value (in (U)) is processed. The nested loops over (L[m]) and (L[l]) produce every combination of indices from the two groups exactly once, and we output the ordered version with (i < j). No other step produces these pairs.

Complexity

  • Sorting 1000 records: (O(N \log N) = O(1000 \log 1000)).
  • Forming groups and outputting distance‑0 pairs: (O(N)).
  • For each of the (M \le 1000) distinct values we generate (30 + 435 = 465) neighbours and binary‑search each in (U) (size (M)). This takes (O(M \cdot 465 \cdot \log M) \le O(1000 \cdot 465 \cdot 10) \approx 4.65 \times 10^6) operations.
  • The total work is (O(N \log N)) with a very small constant, easily fast enough for the given parameters.

Implementation notes

  • The 30 single‑bit masks and the 435 double‑bit masks can be precomputed once.
  • Binary search can be implemented on the array (U) of distinct values.
  • Because the indices within each group (L[m]) are sorted, the pairs ((i,j)) with (i < j) can be emitted by a simple nested loop or by merging two sorted lists if desired, but a double loop is perfectly acceptable for (M \le 1000) and typical group sizes.
  • The algorithm uses only sorting and binary search, staying entirely within the techniques of this chapter.

This completes the solution. ∎