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.

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.

© 2017 Dang-Khoa · Powered by the Academic theme for Hugo.