Given a matrix $M$, and a permutation $P_0$, is it possible to easily count, or easily approximately count, the number of permutation matrices $P$ that satisfy $\|P - M\| = \|P_0 - M\|$?
What about the permutations that satisfy $\|P - M\| \leq \|P_0 - M\|$?
What about list all the permutations $P$ that satisfy either the equality or inequality constraint?
If someone knows how to solve this under some useful matrix norm, or with some restriction on $M$, or some other restriction, please do share.