taocp

Latin squares and a story of computer science history

The content of this note mostly belongs to the first section of TAoCP, Vol4A. Definition Given a square matrix of size $M$ and each element is ${0, 1, \cdots, M-1 }$, we construct a matrix such that for the element $i$ in the set ${0, 1, \cdots, M-1}$ only appears exactly 1 time on every row and column. Examples We have 16 cards which comprises a combination of 4 ranks, i.

Generate the inversion table from an integer sequence

The programming exercise is from TAoCP, Vol3, 5.1.1-6: Design an algorithm that computes the inversion table $b_1, b_2 \cdots b_n$ corresponding to a given permutation $a_1a_2 \cdots a_n$ of ${1, 2, \cdots , n}$, where the running time is essentially proportional to $n\ log n$ on typical computers. I was really stuck on the solution Knuth given in the book. The author also mentioned another approach which actually is a modifination of merge sort.